boj.kr/1939 중량제한 (gold3) 파이썬 풀이

1. 주어진 중량값 중 최소, 최대값을 저장 

2. 1번의 최소, 최대 중량값을 lo, hi에 저장하고 중간값을 mid에 저장한다. mid를 최소무게제한으로 하여 아래 이분탐색 3-5를 반복한다.

3. 최소무게제한을 통과하는 노드만 방문하도록 하여 시작점에서 끝점까지 이동가능한지 여부를 반환하는 bfs를 아래와 같이 실행한다.

3.1. 최소무게제한을 인자로 받고 deque에 시작점을 저장한다.

3.2. 방문체크배열을 노드개수 + 1개 만큼 False으로 초기화하고 시작점을 True로 갱신한다.

3.3. deque에 요소가 없을 때까지 아래를 반복한다.

3.3.1. deque에서 맨 왼쪽 요소를 꺼낸다.

3.3.2. 맨 왼쪽요소에서 갈 수 있는 노드와 그 중량값에 대해 만약 방문하지 않은 노드이고 중량값이 최소중량제한 이상이면 방문체크배열에서 다음 방문할 노드에 대한 값을 True로 갱신하고 deque에 다음 방문할 노드를 추가한다.

3.3.3. 만약 다음 방문할 노드가 목표 도착지점 노드이면 True를 반환하고 bfs 함수를 종료한다.

3.3.4. deque에 요소가 없으나 bfs 함수가 종료되지 않았으면 False를 반환한다.

4. bfs에서 True를 반환했으면 lo를 mid+1 으로 갱신하여 최소중량제한을 늘린다. 그리고 출력값 ans에 mid를 저장한다.

5. bfs에서 False를 반환했으면 hi를 mid-1 으로 갱신하여 최소중량제한을 줄인다.

6. 최대로 가질 수 있는 시작점에서 끝점가지의 최소중량제한인 ans를 출력한다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N+1)]
min_w = 1e9
max_w = -1e9

for _ in range(M):
    (y, x, w) = map(int, input().split())
    min_w = min(min_w, w)
    max_w = max(max_w, w)
    adj[y].append((x, w))
    adj[x].append((y, w))

s, e = map(int, input().split())

from collections import deque

def bfs(limit_w):
    dq = deque()
    dq.append(s)
    visited = [False for _ in range(N + 1)]
    visited[s] = True
    while dq:
        cur = dq.popleft()
        for nxt, weight in adj[cur]:
            if not visited[nxt] and limit_w <= weight:
                visited[nxt] = True
                dq.append(nxt)
                if nxt == e:
                    return True
    return False

lo = min_w
hi = max_w
ans = lo

while lo <= hi:
    mid = (lo+hi)//2
    if bfs(mid):
        lo = mid+1
        ans = mid
    else:
        hi = mid-1

print(ans)

 

너비우선탐색을 통해 시작점에서 끝점까지 갈 수 있는지 여부를 확인하되 매 이동시 마다 최소중량제한을 넘기는지 여부를 조사해야 한다. 왜냐하면 그렇게 해야 이분탐색을 통해 최소중량제한의 최대값을 찾을 수 있기 때문이다.