728x90 백준 32339 대동여지도1 백준 대동여지도 [32339] 파이썬(Python) 코드 + 해설 1. 문제 소개세종이는 조선 시대의 지도인 대동여지도를 보며, 모든 지역을 연결하는 최소 비용의 도로를 설치하고자 한다. 도로에는 세 가지 종류가 있는데, 각각 도보 전용 도로(0), 말 전용 도로(1), 마차 전용 도로(2)이다. 세종이는 최소한의 비용으로 모든 지역을 연결하고자 하며, 만약 최소 비용의 방법이 여러 가지라면 주어진 우선순위에 따라 더 많은 우선순위의 도로를 포함하는 방법을 선택하려 한다.2. 문제 해결 방법이 문제는 최소 스패닝 트리(MST)를 찾는 문제다. 그러나 단순히 최소 비용의 스패닝 트리를 찾는 것에서 그치지 않고, 우선순위에 따라 도로의 종류를 최대화해야 한다.해결 전략은 다음과 같다:도로 우선순위 설정: 입력으로 주어진 도로 종류의 우선순위를 이용해 각 도로 종류에 대한 .. 2024. 11. 17. 이전 1 다음 728x90