'이분 탐색은 정말 간단하면서 강력한 알고리즘'이라는 것을 다시 한번 깨닫게 해주는 문제를 풀이해보겠다.
BOJ 1939 - 중량제한 링크
(2022.10.05 기준 G3)
(치팅 X)
문제
N개의 섬과 그 섬들을 잇는 M개의 다리가 있다. 그리고 각 다리마다 중량제한이 있고 두 개의 섬에 공장이 세워져 있을 때,
공장이 세워져 있는 두 섬을 연결하는 경로 중 한 번에 옮길 수 있는 물품들의 중량의 최댓값
알고리즘
방법이 되게 많아 보인다. 다익스트라도 가능할 것이고, union-find를 이용한 크루스칼도 가능할 것이다. 하지만, 이 문제의 정석은 이분 탐색을 이용한 BFS로 보인다. 그래서 나는 이분 탐색과 BFS를 이용해 보겠다.
풀이
먼저, 다리를 전부 입력받아서 인접 리스트 형태의 그래프를 완성하자.
인접 행렬로 나타내면 메모리가 터진다.C의 범위는 1 ~ 1,000,000,000 이다. 이 범위 안에서 우리는 임의로 물품들의 중량을 조절해가면서 시작으로부터 끝 지점에 도달할 수 있는지 테스트할 것이다. 조절은 어떻게 하냐면, 범위를 절반으로 나누고 범위의 절반인 값을 물품들의 중량으로 설정한 뒤, 시작점에서 BFS를 해보는 것이다.
만약에 그 중량으로 끝에 도착했다면? 출력할 답을 갱신해주고, 물품을 더 실어봐서 다음 테스트를 진행한다. 즉, 범위의 시작을 절반 + 1로 올려서 범위를 좁히는 것이다.
만약에 그 중량으로 끝에 도착하지 못했다면? 물품을 덜 실어서 다음 테스트를 진행한다. 즉, 범위의 끝을 절반으로 줄여서 범위를 좁히는 것이다. (이분 탐색의 방법은 끝을 절반 - 1로 줄이는 것과 절반으로 줄이는 방법이 있다. 난 후자를 선택.)
이러면서 진행하다보면 범위의 시작과 끝이 더 이상 좁혀지지 않게 된다. 그러면 탐색을 종료하여 갱신했던 답을 출력하면 된다.BFS 부분은 따로 설명하지 않겠다. 특별한 부분이 없으므로.
사실 많은 사람들은 이분 탐색할 때, start를 mid + 1로 올리던가, end를 mid - 1로 내린다. 하지만 나는 end를 mid로 내린다. 세그먼트 트리와 똑같이 말이다.
이러면 시간이 더 들지 않겠냐고? 전혀. 오히려 시간이 살짝 줄어들더라. (이유는 모르겠음)
코드
import sys; input = sys.stdin.readline
from collections import deque
def solve():
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)] # 그래프
for _ in range(M):
A, B, C = map(int, input().split())
graph[A].append([B, C])
graph[B].append([A, C])
S, E = map(int, input().split())
# 이분 탐색
start = 1; end = 1000000001 # C의 범위. 끝은 1을 더해주자.
answer = 0
while start != end:
mid = (start + end) // 2 # 수송할 중량
queue = deque([S]) # 시작 지점부터 BFS
visited = [False] * (N + 1)
visited[S] = True
while queue:
here = queue.popleft()
if here == E: # 끝 지점에 갈 수 있으면
answer = mid # 답 갱신
start = mid + 1 # 범위를 mid + 1 ~ end로 좁힌다.
break
for there, limit in graph[here]:
if mid <= limit and not visited[there]: # 다리 중량 제한이 mid보다 같거나 커야 한다.
queue.append(there)
visited[there] = True
else: # 끝 지점에 갈 수 없으면
end = mid # 범위를 start ~ mid로 좁힌다.
print(answer)
solve()여담
BOJ 1348 주차장 풀이가 생각나던 문제였다.
주차장은 이분 매칭 조건이 이분 탐색의 mid, 이 문제는 BFS 조건이 이분 탐색의 mid.
이런 유형의 문제들은 정말 원시적이면서도 정직한 풀이를 원하는 문제 같다.
