Intensity가 최소가 되도록 하는 등산 경로를 찾는 문제
출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤, 다시 원래의 출입구로 돌아오는 경로
그래프 + 간선 별 가중치가 상이 → 다익스트라 알고리즘으로 접근해봅니다.
이때, 예상되는 시간 복잡도는 다음과 같습니다.
탐색 중단 기준
풀이 과정을 반영한 의사 코드는 아래와 같습니다.
<Solution>
Intensity 배열을 생성한다.
Graph를 초기화한다. (각 정점 별 이웃 정점 간의 가중치 저장)
Heap을 초기화한다. (해당 정점에 도착하기 위해 필요한 intensity, 정점 번호)
Heap이 빌때까지 반복:
현재 intensity와 정점 번호 v를 구한다.
if v가 산봉우리 또는 현재 intensity >= Intensity[v]: 탐색 안함
v의 이웃 정점에 대해 아래를 반복:
if 이웃 정점이 출발점 중 한 곳인 경우: 탐색 안함
이웃 정점의 new_intensity = max(Intensity[이웃 정점], 간선 가중치)
if new_intensity < Intensity[이웃 정점]:
Intensity[이웃 정점] = new_intensity
heap에 이웃 정점 추가
Intensity 배열 중, 산봉우리에 해당하는 값만 뽑아옴
최솟값과 해당 산봉우리를 반환
import heapq
from collections import defaultdict
def solution(n, paths, gates, summits):
# DP 배열 생성(출입구에서 해당 정점까지 도달하기 위한 최소 강도)
visited = [1e+9 for _ in range(n+1)]
# 정점 정보 초기화(출입구 및 산봉우리 이외는 쉼터 지점)
gate_dict = {gate: 'ok' for gate in gates}
summit_dict = {summit: 'ok' for summit in summits}
# 가중치 그래프 초기화(각 정점 별 이동 소요 시간)
graph = defaultdict(dict)
for path in paths: # path = [시작점, 도착점, 소요 시간]
graph[path[0]][path[1]] = path[-1]
graph[path[1]][path[0]] = path[-1]
# 완전 탐색 시작(모든 출입구에 대하여 탐색)
heap = []
for gate in gates:
heapq.heappush(heap, (0, gate)) # (해당 정점에 가기 위해 필요한 강도, 정점)
while heap:
intensity, cur_node = heapq.heappop(heap)
if (cur_node in summit_dict) or (intensity > visited[cur_node]):
continue
else:
for neighbor in graph[cur_node].keys():
if neighbor not in gate_dict: # 이웃 정점이 산봉우리 또는 쉼터인 경우 -> DP 배열 업데이트
new_intensity = max(intensity, graph[cur_node][neighbor])
if new_intensity < visited[neighbor]:
visited[neighbor] = new_intensity
heapq.heappush(heap, (new_intensity, neighbor))
# 완전 탐색 결과 정리
answer_list = [
(idx, intensity) for idx, intensity in enumerate(visited)
if idx in summit_dict
]
return list(sorted(answer_list, key=lambda x: (x[1], x[0])))[0]
특정 지점에 도착하기 위해, 필요한 최소한의 비용을 구하는 문제는 크게 두 가지로 분류할 수 있습니다.