12896
-
[백준]12896: 스크루지 민호 - JAVA문제풀이/백준 2021. 8. 23. 15:35
[백준]12896: 스크루지 민호 12896번: 스크루지 민호 구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 www.acmicpc.net 풀이 🪑 탐색과 관련된 문제로 DFS를 사용하여 풀었다. 문제를 잘 이해하는게 중요한 문제 였던 것 같다. 📝 문제의 조건을 살펴보자! N개의 도시를 N-1개의 도로로 연결하며 도로 사이에는 단 한개의 경로만이 존재한다. (트리이다!) 최적의 위치는 소방서에서 다른 도시로 가는 이동 거리 중에 최대가 최소가 되는 지점이다. 도시 간의 거리는 모두 1이다. 도로는 양방향으로 연결되어 있다. 최적의 위치에서 다른 도시에 도착할 때 이동..