[백준 4650] Jungle Roads

1. 문제 설명

Jungle Roads

2. 문제 분석

일반적인 크루스칼 알고리즘 문제. 노드 번호가 정수가 아니라 캐릭터이기 때문에 딕셔너리를 통해 매핑한다.

3. 나의 풀이

import sys
import heapq
import string

def find(node):
    if parents[node] == node: return node
    else:
        parents[node] = find(parents[node])
        return parents[node]

def union(node1, node2):
    root1, root2 = find(node1), find(node2)
    if root1 == root2: return False
    else:
        parents[root2] = root1
        return True

def Krsukal():
    total = 0
    edge_cnt = 0
    while pq:
        cur_cost, node1, node2 = heapq.heappop(pq)
        if union(node1, node2):
            total += cur_cost
            edge_cnt += 1
            if edge_cnt == n-1: break
    if edge_cnt == n-1: return total
    else: return -1

INF = sys.maxsize
letter_num = {letter:num for num, letter in enumerate(string.ascii_uppercase)}
while True:
    n = int(sys.stdin.readline().rstrip())
    if n == 0: break
    pq = []
    for _ in range(n-1):
        edges = list(sys.stdin.readline().rstrip().split())
        node1 = letter_num.get(edges[0])
        for i in range(2, len(edges), 2):
            node2, cost = letter_num.get(edges[i]), int(edges[i+1])
            heapq.heappush(pq, [cost, node1, node2])
    parents = [i for i in range(n)]
    ans = Krsukal()
    print(ans)

좋은 웹페이지 즐겨찾기