[python] 백준 1939 중량제한

 

문제 해결

• 처음에 BFS를 이용해서 문제를 풀려했지만 메모리 초과가 났다.
• 그러면 que안에 적게 넣어서 통과하는지를 확인해야한다.
• 방법이 잘 안떠올라서 다른 풀이를 참고했고 이분 탐색을 이용해서 통과할 수 있는 최댓값이 나올때까지 계속 돌려보는 방법이 있었다.
• 처음에 최솟값 1 최댓값 1000000000을 잡은 후 mid = (low+high)//2를 잡고 mid가 통과하면 low를 한칸 올려주고 통과하지 못하면 high를 한칸 내려주며 계속 시도하는 방식이다. 이를 low<=high일 때 계속 반복한다.

 

CODE

from collections import deque

def solution(mid,s,e):
    visited[s] = 1
    que = deque()
    que.append(s)

    while que:
        now = que.popleft()
        if now == e:
            return True
        for nx, nc in graph[now]:
            if visited[nx] ==0 and mid<=nc:
                que.append(nx)
                visited[nx] = 1
    return False
                

if __name__=='__main__':
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))
    for i in range(1,n+1):
        graph[i].sort(reverse=True)

    s, e = map(int, input().split())
    low, high = 1,  1000000000
    while low <= high:
        visited = [0 for _ in range(n+1)]
        mid = (low+high)//2
        if solution(mid,s,e):
            low = mid + 1
        else:
            high = mid -1
    print(high)