미소를뿌리는감자의 코딩
[백준 2024/02/19] 13905번 세부 본문
728x90
https://www.acmicpc.net/problem/13905
1. 접근 방법
일반적인 최소 신장 트리 문제는, 모든 노드를 접근하되 가장 작은 weight를 지날 수 있도록..이 목표이다.
이번 문제가 다른 점은,
1. 모든 노드를 접근하지 않아도 된다는 점
2. 최소 신장이 아니라, 최대 신장 트리를 구해야 한다는 점이다.
이 점을 유념하여 prim's algorithm을 이용하여 문제를 풀어볼 것이다.
우선 최소 신장 트리 코드에 대한 설명은
https://potatoscatteringsmile.tistory.com/112
위 문제에 자세히 적어 놓았다. -> 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))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/19] 16398번 행성 연결 (1) | 2024.02.19 |
---|---|
[백준 2024/02/19] 1647번 도시 분할 계획 (1) | 2024.02.19 |
[백준 2024/02/17] 1068번 트리 (0) | 2024.02.17 |
[백준 2024/02/15] 2606번 바이러스 (0) | 2024.02.15 |
[백준 2024/02/15] 2667번 단지번호붙이기 (0) | 2024.02.15 |