파이썬 | 백준 | 1939 | 중량제한

solution1 : 배열 이용 

메모리 초과 (무턱대고 사용하지 말 것..)

# 1939, 중량제한
import sys

N, M = map(int, sys.stdin.readline().split())

bridges = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    bridges[a][b] = max(bridges[a][b], c)
    bridges[b][a] = max(bridges[b][a], c)

in1, in2 = map(int, sys.stdin.readline().split())
print(bridges[in1][in2])

solution2  : 이분탐색 + BFS

1(중량제한 최소) ~ max(C) 범위에서 이분탐색(mid) & BFS를 이용해 이동할 수 있는지 확인

이동 가능 → min = mid + 1

이동 불가능 → max = mid - 1

# 1939, 중량제한
import sys
from collections import deque


def bfs(s, e, w):
    visited = [0]*(N+1)
    visited[s] = 1
    q = deque()
    q.append(s)
    while q:
        now = q.popleft()
        if now == e:
            return True

        for x in bridges[now]:
        	# 방문X && 중량제한이 w보다 큰 경우(이동가능한 경우)
            if visited[x[0]] == 0 and x[1] >= w:	
                visited[x[0]] = 1
                q.append(x[0])
    return False

# 이분탐색
def binary_search():	
    global max_
    min_ = 1
    res = 1
    while min_ <= max_:
        m = (min_ + max_) // 2
        # 이동 가능하면 최대값 변경
        if bfs(in1, in2, m):
            res = max(res, m)
            min_ = m+1
        else:
            max_ = m-1
    return res


N, M = map(int, sys.stdin.readline().split())

bridges = [[] for _ in range(N+1)]
max_ = 0
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    max_ = max(max_, c)
    bridges[a].append((b, c))
    bridges[b].append((a, c))

in1, in2 = map(int, sys.stdin.readline().split())

print(binary_search())

 

문제 출처 www.acmicpc.net/problem/1939

1939번: 중량제한