[2022 테크 여름인턴십 코딩테스트] 등산 코스 정하기 #다익스트라 응용

다익스트라 응용 문제

다익스트라 알고리즘만 정확히 이해하고 있으면 조금만 응용해서 풀 수 있다.

핵심은 다음과 같다.

1. 경로중 가장 긴 거리를 pq로 관리한다.

기존의 다익스트라는 경로의 합의 최소를 찾지만, 이 문제에서는 경로중 가장 긴 거리의 최소를 찾는다.

즉 기존에 다음과 같이 경로의 합을 pq에 넣는 방식을

addedD=toD+d
if addedD<nodeDist[toNode]:
    nodeDist[toNode]=addedD
    heapq.heappush(dij,[addedD,toNode])

다음과 같이 바꾸면 되는 것이다.

added_dist = max(visited[node],add_dist)
if added_dist < visited[to_node]:
    visited[to_node] = added_dist
    heapq.heappush(dij,(visited[to_node],to_node))

 

2. 다익스트라는 한번만 수행한다

 다익스트라를 모든 시작점에서 수행하면 시간초과가 발생한다.

시작점의 visited리스트를 0으로 입력해주는 작업을 통해 한번의 다익스트라로 최소 intensity를 찾는 작업을 수행한다.

(이는 문제에서 요구하는 것이 오직 최소 intensity와 그때의 봉우리 이기 때문에 가능한 것이기도 하다)

 

3. intencity가 같은 값이 여러개 일때는, 가장 봉우리가 낮은 번호가 답이 된다는 조건을 잊지 말것

intencity 길이가 같은 경우 사전순으로 가장 봉우리 번호가 낮은것이 답이 된다는 조건이 있다.

이 조건을 만족하기 위해 다익스트라 도중 봉우리를 만나면 바로 종료해서는 안되고, 모든 봉우리를 다 조사한 후 가장 낮은 번호의 봉우리를 골라야 한다.

 

코드

import heapq

def solution(n, paths, gates, summits):
    # graph 세팅
    graph={i:[] for i in range(1,n+1)}
    for a,b,dist in paths:
        graph[a].append((b,dist))
        graph[b].append((a,dist))

    INF=9876543210
    visited=[INF for i in range(n+1)]
    dij = []
    for start_node in gates:
        visited[start_node]=0
        dij.append((0,start_node))

    ans = []
    while(dij):
        d,node = heapq.heappop(dij)
        # print(node,d)
        # print(visited)
        if visited[node]<d:
            continue

        if node in summits:
            ans.append([visited[node],node])
            continue

        for to_node,add_dist in graph[node]:
            added_dist = max(visited[node],add_dist)
            if added_dist < visited[to_node]:
                visited[to_node] = added_dist
                heapq.heappush(dij,(visited[to_node],to_node))

    ans.sort()
    return [ans[0][1],ans[0][0]]