[Python/파이썬] 백준 13905번 세부

13905번: 세부

 

문제

빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.

(금빼빼로 하나의 무게는 1이고, 숭이의 몸무게는 고려하지 않는다.)

입력

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄에는 다리의 정보가 주어진다. 각 줄은 “집의 번호 h1(1≤h1≤N), 집의 번호 h2(1≤h2≤N), 다리의 무게제한 k(1≤k≤1,000,000)” 형식으로 주어진다. (h1집과 h2집은 무게제한이 k인 다리로 연결되어 있다.)

출력

숭이의 출발위치에서 혜빈이의 위치까지 숭이가 들고 갈 수 있는 금빼빼로의 최대 개수를 출력하시오.

코드

import sys
input = sys.stdin.readline
from heapq import heappop, heappush
from collections import deque

def find_parent(x, parent):
    if x != parent[x]:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]

def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    
    if a == b:
        return False
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    return True

n, m = map(int, input().split())
s, e = map(int, input().split())
edges = []
for _ in range(m):
    h1, h2, k = map(int, input().split())
    heappush(edges, (-k, h1, h2))
    
# MST 형성
mst = [[] for _ in range(n+1)]
parent = [i for i in range(n+1)]
while edges:
    w, a, b = heappop(edges)
    if union_parent(a, b, parent):
        mst[a].append((-w, b))
        mst[b].append((-w, a))


# BFS로 s->e 찾아가며 간선의 최소치 기록
ans = int(1e6)
q = deque([(s, int(1e9))])
visited = [False] * (n+1)
visited[s] = True
while q:
    now, min_v = q.popleft()
    if now == e:
        print(min_v)
        exit()
    for w, nx in mst[now]:
        if not visited[nx]:
            q.append((nx, min(min_v, w)))
            visited[nx] = True
            
print(0)    # 연결되어 있지 않아서 전달할 수 없는 경우

 

크루스칼 알고리즘을 이용하여 간선들의 가중치의 합이 최대가 되는 최대 스패닝 트리를 만들고 BFS를 이용하여 s->e까지 가는 경로를 탐색하며 경로에서의 최소치를 구하면 된다. 여기서 주의할 점은 보통 최소 스패닝 트리(Minimum Spannign Tree)를 만들 때 크루스칼을 많이 사용하는데 이 문제는 간선들이 최대치로 이어져야 하므로 최대 스패닝 트리(Maximum Spanning Tree)를 만들어야 한다. 이것은 heapq에 넣어줄 때 입력에서 무게제한으로 주어진 k값을 음수로 넣어주면 된다.

 

문제에 명시되어 있지 않아서 그래프가 연결되어 있지 않은 경우는 고려하지 않아서 계속 틀렸는데 마지막에 print(0)을 넣어주었더니 해결됐다...