백준 대동여지도 [32339] 파이썬(Python) 코드 + 해설

백준 32339 대동여지도 문제

1. 문제 소개

세종이는 조선 시대의 지도인 대동여지도를 보며, 모든 지역을 연결하는 최소 비용의 도로를 설치하고자 한다. 도로에는 세 가지 종류가 있는데, 각각 도보 전용 도로(0), 말 전용 도로(1), 마차 전용 도로(2)이다. 세종이는 최소한의 비용으로 모든 지역을 연결하고자 하며, 만약 최소 비용의 방법이 여러 가지라면 주어진 우선순위에 따라 더 많은 우선순위의 도로를 포함하는 방법을 선택하려 한다.

2. 문제 해결 방법

이 문제는 최소 스패닝 트리(MST)를 찾는 문제다. 그러나 단순히 최소 비용의 스패닝 트리를 찾는 것에서 그치지 않고, 우선순위에 따라 도로의 종류를 최대화해야 한다.

해결 전략은 다음과 같다:

1. 도로 우선순위 설정: 입력으로 주어진 도로 종류의 우선순위를 이용해 각 도로 종류에 대한 우선순위 랭크를 매긴다.
2. 간선 정렬 기준 설정: 간선을 정렬할 때, 비용을 오름차순으로 정렬하고, 비용이 같다면 우선순위 랭크에 따라 정렬한다. 우선순위 랭크가 낮을수록 우선순위가 높다.
3. 크루스칼 알고리즘 적용: 정렬된 간선을 순서대로 확인하며, 유니온-파인드(Union-Find) 자료구조를 이용해 사이클이 생기지 않도록 간선을 선택한다.
4. 도로 종류별 통계 수집: MST를 구성하는 동안 선택된 각 도로 종류별로 개수와 비용을 누적하여 계산한다.
5. 결과 출력: 총 비용과 도로 종류별 설치 개수 및 비용을 출력한다.

우선순위 랭크 매기기 예시:

• 주어진 우선순위가 [0, 1, 2]라면,
  • 도보 전용 도로(0)의 우선순위 랭크는 0
  • 말 전용 도로(1)의 우선순위 랭크는 1
  • 마차 전용 도로(2)의 우선순위 랭크는 2

3.  백준 대동여지도 32339 파이썬(Python) 정답 코드

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

N, M = map(int, input().split())
priority_order = list(map(int, input().split()))
priority_rank = {k: i for i, k in enumerate(priority_order)}

edges = []
for _ in range(M):
    u, v, w, k = map(int, input().split())
    edges.append((w, priority_rank[k], u, v, k))

edges.sort(key=lambda x: (x[0], x[1]))

parent = [i for i in range(N+1)]

def find(u):
    while parent[u] != u:
        parent[u] = parent[parent[u]]
        u = parent[u]
    return u

def union(u, v):
    ru = find(u)
    rv = find(v)
    if ru != rv:
        parent[rv] = ru
        return True
    return False

total_cost = 0
road_count = [0, 0, 0]
road_cost = [0, 0, 0]
selected_edges = 0

for w, prio, u, v, k in edges:
    if union(u, v):
        total_cost += w
        road_count[k] += 1
        road_cost[k] += w
        selected_edges += 1
        if selected_edges == N - 1:
            break

print(total_cost)
for k in [0, 1, 2]:
    print(f"{road_count[k]} {road_cost[k]}")

4. 백준 대동여지도 32339 정답 코드 해설

1. 입력 처리 및 우선순위 설정:
   • priority_order를 입력받고, 각 도로 종류에 대한 priority_rank 딕셔너리를 생성한다.
   • 각 간선을 입력받으면서 (비용, 우선순위 랭크, 시작점, 끝점, 도로 종류)의 형태로 edges 리스트에 저장한다.
2. 간선 정렬:
   • edges.sort(key=lambda x: (x[0], x[1]))를 통해 비용을 기준으로 오름차순 정렬하고, 비용이 같을 경우 우선순위 랭크에 따라 정렬한다.
3. 유니온-파인드(Union-Find) 구현:
   • parent 배열을 이용해 각 정점의 대표 노드를 저장한다.
   • find(u): 경로 압축을 이용해 정점 u의 대표 노드를 찾는다.
   • union(u, v): 두 정점 u, v를 연결하고, 사이클이 생기지 않으면 True를 반환한다.
4. 크루스칼 알고리즘 적용 및 도로 통계 수집:
   • 정렬된 간선을 순회하며, union(u, v)가 True인 경우 MST에 간선을 추가한다.
   • 간선을 추가할 때마다 총 비용과 도로 종류별 개수 및 비용을 업데이트한다.
   • selected_edges가 N - 1에 도달하면 MST 구성이 완료되므로 반복을 종료한다.
5. 결과 출력:
   • 총 비용을 출력한다.
   • 도로 종류별로 설치 개수와 비용을 출력한다. 도로 종류는 0부터 2까지 순서대로 출력한다.

 

5.  문제 해결 추가 설명

• 우선순위 랭크의 중요성: 우선순위 랭크를 이용해 간선을 정렬함으로써, 최소 비용의 MST 중에서도 우선순위가 높은 도로를 최대한 많이 포함할 수 있다.
• 시간 복잡도: 간선의 정렬에 O(MlogM), 크루스칼 알고리즘에 O(Mα(N))의 시간이 소요되며, 전체적으로 O(MlogM)으로 제한 시간 내에 충분히 동작한다.
• 유니온-파인드 최적화: 경로 압축(Path Compression)을 적용하여 유니온-파인드의 효율성을 높였다.

 

6.  백준 대동여지도 32339 제출 결과

백준 대동여지도 32339 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.