[백준]1939번 : 중량제한

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

1939번: 중량제한

이 문제는 bfs만으로는 풀 수 없는 문제이다.

왜냐하면

 

 

 

BFS만을 이용했을 때의 한계점

bfs의 시간복잡도

• 인접 리스트의 경우 O(V+E)
•  인접 행렬의 경우 O(V^2)

이동하는 다리들 중 최댓값

• O(n)

 

따라서 기존 bfs만을 이용했을 때 총 O(n(V+E))의 시간복잡도로 시간초과가 발생한다

시간을 줄이기 위하여 이진탐색을 이용한다.

 

이진 탐색

• 무게의 최솟값을 s, 최댓값을 e로 할당 한 뒤 중간값(m)을 이용하여 탐색
• 만약 중간값으로 bfs 성공 시 s = m+1
• 중간 값으로 bfs 실패 시 e = m-1

 

 

 

 

전체 코드

import sys
from collections import deque

def bfs(weight):
    visited = [False for _ in range(N)]
    visited[start] = True
    Q = deque()
    Q.append(start)
    while Q:
        current = Q.popleft()
        if current == end:
            return True
        for next_weight,next in G[current]:
            if not visited[next] and next_weight >=weight:
                visited[next] = True
                Q.append(next)
    return False

input = sys.stdin.readline
N,M = map(int,input().split())
G= [[] for _ in range(N)]

for _ in range(M):
    a,b,c  =map(int,input().split())
    a,b = a-1,b-1
    G[a].append((c,b))
    G[b].append((c,a))
start,end = map(int,input().split())
start,end = start-1,end-1

s,e = 1, 1_000_000_000
ans = s
while s<=e:
    m = (s+e)//2
    if bfs(m):
        ans = m
        s = m+1
    else:
        e = m -1
print(ans)

​