🔴 문제 개요
제1회 류호석배 알고리즘 코딩 테스트 문제로 출제되었던 문제입니다. 주어진 A에서 B까지 C원 이하로 갈 수 있는 경로에서 가장 비싼 골목 가중치의 최소를 구하면 되는 문제입니다.
제한 사항
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 500,000
- 1 ≤ C ≤ 10e14
- 1 ≤ 골목 별 수금액 ≤ 10e9
- 1 ≤ A, B ≤ N, A ≠ B
- 골목이 잇는 교차로의 번호는 서로 다르다.
- 골목은 양방향이다.
문제 유형
A에서 B까지 가는 최단 경로를 구해야하기 때문에 우선 다익스트라 알고리즘을 적용할 수 있습니다. 추가로, 가장 비싼 골목 가중치를 Maximum이라고 두었을 때, C원 이하로 A에서 B까지 갈 수 있는지 판단하는 결정 문제를 C원 이하로 A에서 B까지 갈 수 있는 가장 작은 Maximum을 구하는 최적화 문제로 풀어낼 수 있기 때문에, 파라메트릭 서치의 개념도 도입합니다.
🟠 Solution
우선 input을 받는 부분입니다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = 10e14
N, M, A, B, C = map(int, input().rstrip().split())
adj = [[] for _ in range(N + 1)]
costs = []
for _ in range(M):
u, v, w = map(int, input().rstrip().split())
adj[u].append((w, v))
adj[v].append((w, u))
costs.append(w)- 골목은 양방향임에 유의하여 인접 리스트를 받습니다.
- 다익스트라 알고리즘의 heap 연산을 위해 (가중치, 인접 노드) 형식으로 경로를 저장합니다.
- costs는 최적화 문제를 해결할 때 활용하기 위해 별도로 cost를 저장합니다. 추후 설명하도록 하겠습니다.
이제 결정 문제와 최적화 문제를 정의하겠습니다.
- 결정문제
- 가장 비싼 골목 가중치를 Maximum이라고 두었을 때, C원 이하로 A에서 B까지 갈 수 있는가?
- 최적화 문제
- A에서 B까지 갈 수 있는 가장 작은 Maximum은?
위와 같이, 결정 문제를 통해 최적화 문제를 효율적으로 풀이해내기 위해 파라메트릭 서치의 개념을 도입하겠습니다. 우선, 결정 문제에 대한 메서드입니다.
def djk(st: int, en: int, maximum: int) -> bool:
"""
st에서 en까지 가장 비싼 골목을 maximum이라고 두었을 때 최종 C원 이하로 갈 수 있는지의 여부를 반환한다.
"""
# 초기화
dist = [INF for _ in range(N + 1)]
dist[st] = 0
heap = [(0, st)]
while heap:
w, v = heappop(heap)
# 이미 더 적은 경로로 업데이트 된 경우
if dist[v] != w:
continue
for nxt_w, nxt_v in adj[v]:
# 거리 업데이트
cost = w + nxt_w
# 골목의 가중치는 maximum을 넘으면 안됨
if nxt_w <= maximum and cost < dist[nxt_v]:
dist[nxt_v] = cost
heappush(heap, (cost, nxt_v))
# C원 이하로 갈 수 있는지 여부 반환
return dist[en] <= C- 일반적인 다익스트라 알고리즘을 그대로 적용하되,특정 경로를 통한 최단 경로를 업데이트 할 때, 골목의 가중치는 maximum을 넘으면 안됩니다.
- 최종적으로 목적지까지의 최단 경로가 C원 이하인지를 반환합니다.
결정 문제에 대한 메서드를 위와 같이 정의했을 때, 아래와 같이 최적화를 수행할 수 있습니다.
# 결정문제를 통해 최소 maximum을 찾아낸다.
costs.sort() # 이진 탐색을 적용하기 위해 값 정렬
low, high = 0, len(costs) - 1
answer = INF
while low <= high:
mid = (low + high) // 2
if djk(A, B, costs[mid]): # maximum을 mid로 설정했을 때 결정 문제를 만족하면
high = mid - 1 # maximum을 작게하여 탐색
if costs[mid] < answer: # 최소값 업데이트
answer = costs[mid]
else: # 결정 문제를 만족하지 못하면
low = mid + 1 # maximum을 크게하여 탐색
print(answer if answer != INF else -1)- 최적화 과정은 기본적으로 이진 탐색을 통해 이루어집니다.
- maximum의 범위를 결정 문제를 만족하는 지에 따라 크게 하거나 작게 하여 최적화가 이루어지는 것입니다.
- 이진 탐색의 범위는 앞서 입력 받은 cost의 범위 내로 제한합니다.
- 문제의 조건인
1 ≤ 골목 별 수금액 ≤ 10e9범위로 탐색을 수행하면 시간초과가 발생합니다.
- 문제의 조건인
- 최종적으로 결정문제를 한 번이라도 만족하여 값이 업데이트 된 answer를 출력합니다. answer가 단 한 번도 업데이트 되지 못했다면, 지금 가진 돈으로는 절대로 목표 지점을 갈 수 없다는 것이므로 -1을 출력합니다.
🟡 후기
- 최단 경로 알고리즘인 다익스트라 알고리즘을 공부하던 중에 파라메트릭 서치를 통한 최적화 과정이 함께 이루어져야 하는 이번 문제를 접해 풀이하게 되었습니다.
- 개인적으로 굉장히 유익했던 문제라고 생각했고, 풀이를 문서화와 함께 공유하고 싶어 포스팅까지 이어졌습니다. 이후 다익스트라 알고리즘의 개념까지 추가로 포스팅하도록 하겠습니다.
Grow Exponentially