반응형 최소스패닝트리1 백준 13418번 학교 탐방하기 - C++(cpp) 풀이 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 2. 오르막길에는 가중치 1, 내리막길에는 가중치 0을 준다. 3. 최악의 경로는 최대 스패닝 트리, 최적의 경로는 최소 스패닝 트리이다. 1. 최소한의 길을 선택해서 모든 건물을 탐방해야 하므로, 스패닝 트리를 구하면 된다. 모든 건물을 방문하는 데 필요한 최소한의 길을 선택해야 한다. 즉, 최소 연결 부분 그래프 = 스패닝 트리를 구하면 된다. 모든 건물을 방문하려면 왔던 길을 되돌아가야 하기 때문에 문제가 생기지는 않을까 싶지만, 오르막길은 되돌아갈 때는 내리막길이 되고, 또 내리막길이 되돌아올 때 오르막길이 되는 것은 무효 처리하기 때문에 단순히 스패닝 트리를 구해도 문제가 되지 않는다. 2. 오르막길에는 가중.. 2022. 4. 15. 이전 1 다음 반응형
