•
•
이분탐색 말고 BFS, 다익스트라 만으로도 풀 수 있다고 한다. 다시 풀어보자!
문제
N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.
영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.
한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.
요령
입력
•
첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤ C ≤1,000,000,000)가 주어진다.
•
마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다.
구해야 하는 값이 중량 C인 상황에서 C의 범위가 1 ≤ ≤ 1,000,000,000 의 큰 범위이다. 따라서 다익스트라, BFS 등을 통한 그래프 알고리즘만으로 문제를 해결하지 못하고 C의 값을 찾는 경우라면 Log(N) 알고리즘을 사용해야 한다.
풀이
•
기본 알고리즘
#Loop
1. 이분탐색을 통해 특정 다리의 무게 C 를 설정한다.
2. BFS로 그래프를 탐색하며 C 이상의 다리를 사용해서 목적지에 도착할 수 있는지 검사한다
3. 목적지에 도착할 수 있으면 다리의 무게 C를 증가시키고
도착할 수 없다면 다리의 무게 C를 감소시킨다.
Python
복사
•
bfs 함수 (그래프 탐색)
- c = 이분탐색을 통해 정한 다리의 무게값
def bfs(c):
q = deque()
visit = [False] * (N + 1)
q.append(f1)
visit[f1] = True
while q:
cur = q.popleft()
if visit[f2] == True: # 목적지에 갈 수 있으면 탐색 중단해 성능 향상
return True
for y, weight in arr[cur]:
if visit[y] == 0 and weight >= c: # 다리의 하중이 c 이상인 경우에만 탐색 진행
visit[y] = True
q.append(y)
return visit[f2]
Python
복사
•
입력
N, M = map(int, input().split()) # 섬의 개수, 다리의 개수
arr = [[] for _ in range(N + 1)]
left = 1000000000 # 이진탐색 left값
right = 1 # 이진탐색 right 값
for _ in range(M):
a, b, c = map(int, input().split())
arr[a].append((b,c))
arr[b].append((a,c))
left = min(left, c)
right = max(right, c)
f1, f2 = map(int, input().split()) # 섬의 개수, 다리의 개수
Python
복사
•
Main 함수 동작
result = 0
while left <= right:
mid = (left + right) // 2
if bfs(mid): # 목적지에 갈 수 있음
left = mid + 1 # 무게 증가
result = mid
else:
right = mid - 1
print(result)
Python
복사
중요
1.
Python의 List 만으로도 queue 동작을 구현할 수 있지만 deque에 비해 성능이 나쁘다. deque 사용법을 익혀서 사용하자!
from collections import deque
q = deque()
Python
복사
