백준 1939번 파이썬 문제풀이(중량 제한) - (1. 최대힙 다익스트라, 2. 유니온 파인드)

---

해당 문제는 풀이가 많이 존재할 수 있으나 크게 생각나는 2가지 방법으로 구현했다.

 

1. 최대힙을 이용한 다익스트라

 

2. 중량을 내림차순 정렬 후 유니온 파인드

---

 

1. 최대힙을 이용한 다익스트라

import heapq
import sys

input = sys.stdin.readline


def dijkstra(v1, v2):
    global ans
    q = []
    heapq.heappush(q, (-(1 << 60), v1))

    while q:

        cost, cur = heapq.heappop(q)
        cost = (-cost)

        if cur == v2:
            print(cost)
            return
        # 만약 현재 비용이 구한 비용보다 적다면 실행x
        if cost < distance[cur]:
            continue

        for nxt, nxt_cost in graph[cur]:
            # 만약 다음노드에 저장된 중량값이 현재까지 구한 cost와 다음 노드의 중량보다 작다면
            if distance[nxt] < nxt_cost and distance[nxt] < cost:
                distance[nxt] = min(cost, nxt_cost)  # 그중 작은값을 최대 중량으로 저장 후
                heapq.heappush(q, (-distance[nxt], nxt))  # 최대 값으로 힙에 넣어준다


N, M = map(int, input().split())

graph = [[] for _ in range(N + 1)]
for i in range(M):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))
    graph[b].append((a, cost))

v1, v2 = map(int, input().split())
distance = [0] * (N + 1)
dijkstra(v1, v2)

 

2. 중량을 내림차순 정렬 후 유니온 파인드

import sys

input = sys.stdin.readline


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


def union_(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return

    parent[a] = b


N, M = map(int, input().split())

graph = []
for i in range(M):
    a, b, cost = map(int, input().split())
    graph.append([a, b, cost])

graph.sort(key=lambda x: -x[2])  # 가장 중량이 큰 다리를 기준으로 내림차순
parent = [i for i in range(N + 1)]  # 부모를 자기자신으로 설정

v1, v2 = map(int, input().split())

for i in range(M):
    union_(graph[i][0], graph[i][1])  # 두개의 노드를 한 연결요소로 넣어준다

    if find(v1) == find(v2):  # 만약 두 다리가 연결되었다면
        print(graph[i][2])  # 그 때의 중량이 최대 중량이 됨으로 그 값을 출력 후
        break  # 반복문 탈출