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

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

1939번: 중량제한

---

• 문제 : 

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

 

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

 

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

이분탐색과 그래프 탐색 문제였습니다.

 

알고리즘의 흐름입니다.

 

1. 양방향 그래프 구현

 

2. 이분탐색의 범위 지정. 

  저의 경우에는 left = 1, right 는 입력받은 다리의 하중들의 max값을 사용하였습니다.

 

3. 이분탐색 구현. 

  이분탐색의 search값은 무게입니다. 택배의 무게를 mid로 잡고 이 값으로 bfs를 실시합니다.

 

4. bfs 구현

  bfs의 인자값은 weight로 이 값이 도착점으로 갈 수 있냐, 없냐를 따지는 방식으로 구현하였습니다.

bfs탐색이 종료된 후에 visited배열의 t (도착점)이 초깃값이라면 도착할 수 없으므로 False를, 아니라면 True를 리턴하게 하였습니다.

 

5. 이분탐색 범위 조정

 mid값에서 bfs결과 해당 무게는 도착점까지 옮길 수 있으면 left를 mid+1로 바꿔주어 범위를 재 조정하고 다시 bfs를 실시합니다. 이분탐색이 종료될 때까지 bfs를 실행하게 됩니다.

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
graph = [[] for _ in range(N+1)]
left = 1
right = 0
answer = 0
def bfs(weight):  # 무게(wieght)를 기준으로 BFS탐색
    queue = deque()
    queue.append(f) #시작점은 무조건 f
    visited = [0 for _ in range(N+1)]
    visited[f] = 0
    while queue:
        x = queue.popleft()
        for i,w in graph[x]:
            if w >= weight and visited[i] == 0:
                queue.append(i)
                visited[i] = 1
    if visited[t] != 0: return True  #갈 수 있을 때
    return False # 못 갈 때

for _ in range(M): #양방향 그래프 구현
    a,b,c = map(int,input().split())
    right = max(right,c) # 이분 탐색의 끝 점을 정의하기 위함
    graph[a].append([b,c])
    graph[b].append([a,c])
f,t = map(int,input().split())  # 출발점, 도착점

while left <= right:
    mid = (left+right)//2
    if bfs(mid): # 출발점에서 도착점까지 무게 mid를 옮길 수 있는 경우
        answer = mid
        left = mid+1
    else: # 못 옮기는 경우
        right = mid -1
print(answer)