문제 링크
풀이 과정
•
Intensity가 최소가 되도록 하는 등산 경로를 찾는 문제
◦
Intensity → 휴식 없이 이동하는 시간 중 가장 긴 시간
•
출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤, 다시 원래의 출입구로 돌아오는 경로
◦
출입구에서 시작하여 산봉우리에 최초로 도착하는 경로만 찾으면 됩니다! (하산은 동일한 경로를 이용하면 되므로)
•
그래프 + 간선 별 가중치가 상이 → 다익스트라 알고리즘으로 접근해봅니다.
•
이때, 예상되는 시간 복잡도는 다음과 같습니다.
◦
출입구(시작점)의 수만큼, 다익스트라 알고리즘을 적용합니다.
◦
출입구: n, 노드의 수: V, 간선의 수: E라고 합시다.
◦
따라서, 시간 복잡도는 O(n*(V+E))입니다.
◦
이때, 1 ≤ n ≤ 50,000 / 1 ≤ V ≤ 50,000 / 1 ≤ E ≤ 200,000 이므로, 모든 경우의 수를 고려하면 시간 초과가 발생합니다.
◦
따라서, 탐색 경우의 수를 줄이는 기준을 찾아야합니다!
•
탐색 중단 기준
◦
현재 지점이 산봉우리인가?
◦
산봉우리에 도착하기 전에, 다른 출입구에 도착했는가?
◦
현재 등산 경로를 통해 A 정점에 도착했을 때, 현재 intensity가 기존 intensity 이상인가?
▪
각 정점 별 최소 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 배열 중, 산봉우리에 해당하는 값만 뽑아옴
최솟값과 해당 산봉우리를 반환
Plain Text
복사
전체 코드
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]
Python
복사
유사 문제
특정 지점에 도착하기 위해, 필요한 최소한의 비용을 구하는 문제는 크게 두 가지로 분류할 수 있습니다.
•
같은 지점에 접근할 때, 비용을 갱신할 수 있는 경우
•
같은 지점에 접근할 때, 비용을 갱신하면 안되는 경우