[백준 2024/02/19] 13905번 세부

https://www.acmicpc.net/problem/13905

13905번: 세부

 

1. 접근 방법

일반적인 최소 신장 트리 문제는, 모든 노드를 접근하되 가장 작은 weight를 지날 수 있도록..이 목표이다.

 

이번 문제가 다른 점은,

1. 모든 노드를 접근하지 않아도 된다는 점

2. 최소 신장이 아니라, 최대 신장 트리를 구해야 한다는 점이다.

 

이 점을 유념하여 prim's algorithm을 이용하여 문제를 풀어볼 것이다.

 

우선 최소 신장 트리 코드에 대한 설명은 

https://potatoscatteringsmile.tistory.com/112

[백준 2024/02/13] 1922번 네트워크 연결

위 문제에 자세히 적어 놓았다. -> Prim's Algorithm

 

우선 최소 신장 트리를 구하기 위해서 트리에 값을 넣어줄 때, weight * -1 을 해서 넣어주었다.

이를 통해 원래 3 5 1 이 들어가야 한다면, pop이 1 -> 3 -> 5로 되어야 하지만, -1을 곱해주었기 때문에

-5 -> -3 -> -1 로 pop이 될 것이다. 여기에, -1을 다시 곱해주어 원하는 값을 얻어낼 수 있다.

 

다음으로, 1번 노드에서 5번 노드로 접근할 때를 구하는 것이기 때문에, 

visited[5] 가 True가 아닐 때만 while 문을 돌려주었다. -> while 문의 탈출 조건

 

접근할 때마다, weight_bridge라는 list에 weight를 저장해주었다.

 

이후 min(weight_bridge)를 구해주어, 가지고 갈 수 있는 무게제한을 맞추어주었다.

 

2. 코드

import heapq

nodes, edges = map(int, input().split())
start, end = map(int, input().split())

node_list = [[] for _ in range(nodes + 1)]
visited = [False] * (nodes + 1)
heap = []
weight_bridge = []

for i in range(edges):
    n1, n2, w = map(int, input().split())
    node_list[n1].append((w, n2))
    node_list[n2].append((w, n1))

visited[start] = True

for w, node in node_list[start]:
    heapq.heappush(heap, ( -1*w, node))

notFound = False
node = start
while not visited[end]:
    if len(heap) == 0:
        notFound = True
        break
    w, node = heapq.heappop(heap)
    if not visited[node]:
        weight_bridge.append(-1*w)
        visited[node] = True
        for w, node in node_list[node]:
            heapq.heappush(heap, (-1*w, node))

if notFound:
    print(0)
else:
    print(min(weight_bridge))