최소 신장트리 백준 문제 풀기
흔히 Minimum Spanning Tree라는 형태로 많이 접하는 최소 신장 트리 문제인데, 단순히 DFS & BFS 뿐만 아니라 그래프를 활용하는 문제는 최소신장트리와 다익스트라, 그리고 플로이드 워셜 알고리즘 등 다양한 그래프 알고리즘 이론들을 기반으로 문제가 출제 되곤 한다.
그 중 백준에서 기초 문제로 나오는 상근이의 여행을 다뤄보도록 하자.
테스트 케이스 해석하느라 꽤 애먹었는데, 간선 사이의 비중 값도 없고, 그냥 연결만 되어 있는 경우라 각 간선을 1로 보고 노드 한 개를 이동할 때마다 +1 형태로 코드를 짜게 된다.
다만, graph 변수에 0번째 인덱스는 활용하지 않고, 우리가 실질적으로 활용하는 부분은 1 이후이기 때문에 (u,v 값) 해당 내용을 유의하면서 코딩하면 될 것 같다.
문제만 보면 최소 신장 트리라고 받아들여지기 보다는 그냥 DFS 문제를 한 개 더 풀었다는 느낌인 것 같다.
Ryan
