[BOJ] 1197

less than 1 minute read

최소 스패닝 트리

1197번 https://www.acmicpc.net/problem/1197

Kruskal algorithm을 이용하는 전형적인 문제입니다.

  1. 모든 edge들을 가중치에 대한 오름차순으로 정렬해줍니다.
  2. 가중치가 낮은 다리부터 확인하며 다리를 연결했을 때 사이클이 생기지 않는다면 그 다리를 연결해줍니다.

BOJ_17472: 다리 만들기 2 문제도 해법이 비슷합니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1197.cpp

Categories:

Updated:

Leave a comment