[백준] 1939번 : 중량제한 - Python(파이썬)

 

www.acmicpc.net/problem/1939

1939번: 중량제한

 

풀이

• BFS : dequeue 사용 : 가중치 제한, 도착, 끝 & visit 리스트 :  경로 기록, 한번의 이동 체크
• 이진탐색 : 이동 가능한 최대 중량

 

코드

import sys
from collections import deque
input=sys.stdin.readline

n,m=map(int, input().split())
adj=[[] for _ in range(n+1)]

for _ in range(m):
    a,b,w=map(int,input().split())
    adj[a].append((b,w))
    adj[b].append((a,w))

start,end=map(int,input().split())
min_=1
max_=1000000000


def bfs(c):
    queue=deque()
    queue.append(start)
    visit=[False]*(n+1)
    visit[start]=True
    while queue:
        x=queue.popleft()
        for y,weight in adj[x]:
            if not visit[y] and c<=weight:
                queue.append(y)
                visit[y]=True
    
    return visit[end]

while min_<=max_:
    mid=(min_+max_)//2

    if bfs(mid):
        result=mid
        min_=mid+1
    else:
        max_=mid-1

print(result)

 

 

햇갈렸던 점

#(1) 양방향으로 오고 갈 수 있으므로 간선을 두번 저장
for _ in range(m):
    a,b,w=map(int,input().split())
    adj[a].append((b,w))
    adj[b].append((a,w))
    
#(2) list는 zero-indexing이므로 섬 번호로 깔끔하게 인덱스를 매기고 싶으면 n+1해줘야함
#(3) BFS 알고리즘 -> 시작점부터 끝 점까지 중량 제한을 모두 확인
#(4) deqeue -> 양쪽으로 효율적으로 추가/삭제, append : 오른쪽 추가, leftpop : 왼쪽 삭제
#(5) visit -> 방문:True, 방문 X : False
def bfs(c):
    queue=deque()
    queue.append(start)
    visit=[False]*(n+1)
    visit[start]=True
    while queue:
        x=queue.popleft()
        for y,weight in adj[x]:
            if not visit[y] and c<=weight:
                queue.append(y)
                visit[y]=True
    
    return visit[end]