[백준/Python] 1939번 - 중량제한

문제

백준 - 1939번 중량제한

해결 과정

1. 입력 받기

• graph = [[], [(2, 2), (3, 3)], [(1, 2), (3, 2)], [(1, 3), (2, 2)]]
  ex) 1번 섬과 2번 섬을 잇는 다리의 중량 제한은 2 ( ⬌ 2번 섬과 1번 섬을 잇는 다리의 중량 제한은 2)
• one, two : 공장이 있는 섬

2. 이분탐색

• 이분탐색 전 그래프 정렬
• 이분탐색으로 한번의 이동으로 옮길 수 있는 물품들의 중량의 최대값 찾기
• start, end: 중량 제한의 최소, 최대값

3. BFS

• 해당 중량 (mid)가 시작섬에서 끝섬까지 갈 수 있는 지 확인하는 것
• 시작은 one, 도착은 two로 고정하고 mid(중량)만 확인하는 것
• 큐가 빌 때까지 반복
  • now와 two가 같다면 갈 수 있는 것으로 True
  • now와 연결된 섬의 번호와 중량을 하나씩 확인한다.
    해당 섬을 방문하지 않았고, 최대 중량(mid)보다 해당 중량이 크거나 같다면 이동 가능한 것으로 큐에 넣고, 방문처리해준다.

풀이

import sys
from collections import deque

# 3. BFS 구현
def bfs(mid):
  visited[one] = 1
  q = deque([one])
  while q:
    now = q.popleft()
    if now == two:
      return True
    for nx, nc in graph[now]:
      if visited[nx] == 0 and mid <= nc:
        q.append(nx)
        visited[nx] = 1
  return False

# 1. 입력 받기
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
  a,b,c = map(int,sys.stdin.readline().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

# 공장 위치
one, two = map(int,sys.stdin.readline().split())

# 2. 이분탐색
# 이분탐색 전 정렬 필요  
for i in range(1, n + 1):
  graph[i].sort(reverse=True)
  
start,end = 1, 1000000000

while start <= end:
  visited = [0 for _ in range(n + 1)]
  mid = (start + end) // 2
  if bfs(mid):
    start = mid + 1
  else:
    end = mid - 1
    
print(end)