[Python] 백준 1939 - 중량제한 문제 풀이

Overview

BOJ 1939번 중량제한 Python 문제 풀이
분류: Shortest Path (최단거리), Dijkstra, Binary Search (이분탐색)

---

문제 페이지

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

---

풀이 코드 1 - 다익스트라 알고리즘

from sys import stdin, maxsize
from heapq import heappush, heappop
from collections import defaultdict


def dijkstra(start: int, end: int, graph: defaultdict) -> int:
    weights = defaultdict(int)
    hq = [(-maxsize, start)]

    while hq:
        weight, node = heappop(hq)
        if -weight < weights[node]:
            continue

        for neighbor, w in graph[node]:
            temp = min(-weight, w)
            if temp > weights[neighbor]:
                heappush(hq, (-temp, neighbor))
                weights[neighbor] = temp

    return weights[end]


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(m):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))
        graph[b].append((a, w))
    start, dest = map(int, stdin.readline().split())

    print(dijkstra(start, dest, graph))


if __name__ == "__main__":
    main()

Dijkstra 알고리즘을 응용한 풀이. 일반 다익스트라 알고리즘에서는 간선의 길이를 기준으로 최단거리를 업데이트 하지만, 여기에서는 제한 중량을 기준으로 업데이트한다.

---

풀이 코드 2 - 이진 탐색, BFS

from sys import stdin
from collections import defaultdict, deque


start, dest = 0, 0
graph = defaultdict(list)


def bfs(weight: int) -> bool:
    visit = defaultdict(bool)
    visit[start] = True
    dq = deque([start])

    while dq:
        node = dq.popleft()
        for neighbor, limit in graph[node]:
            if not visit[neighbor] and weight <= limit:
                if neighbor == dest:
                    return True
                visit[neighbor] = True
                dq.append(neighbor)
    return False


def main():
    def input():
        return stdin.readline().rstrip()
    global start, dest

    n, m = map(int, input().split())
    low, high = 0, 0
    for _ in range(m):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))
        graph[b].append((a, w))
        high = max(w, high)
    start, dest = map(int, stdin.readline().split())

    res = 0
    while low <= high:
        mid = low + (high - low) // 2
        if bfs(mid):
            res = mid
            low = mid + 1
        else:
            high = mid - 1

    print(res)


if __name__ == "__main__":
    main()

Binary search를 이용하여 중량을 정하고, BFS 탐색을 통해 목적지까지 도달할 수 있는지 여부를 통해 답을 구한다.