[프로그래머스] 등산코스 정하기 (python)

 

1️⃣ 문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/118669

 

2️⃣ 기억해야 했던 개념들

 

- 기본 다익스트라 개념

- 다익스트라의 시작 정점은 여러 개일 수 있다. 

 

3️⃣ 풀이 과정

문제를 요약하면, 여러 개의 출입구 중 하나의 출입구에서 시작하여 여러 개의 산봉우리 중 하나의 산봉우리에 방문하고 다시 동일한 출입구로 내려올 때까지의 Intensity를 최소화해야 한다.

이때, intensity는 출입구 -> 쉼터 -> 산봉우리를 이동할 때 휴식 없이 이동해야 하는 가장 긴 시간을 말한다. 

 

1. 다익스트라를 써야하는 건 알겠는데.. 각 출입구마다 다 돌면서 다익스트라로 돌면 안 되나?

안 된다. 정점의 개수는 최대 50,000개, 간선은 최대 200,000개이다. 우선순위큐로 다익스트라를 구현했다고 하면 G(출입구 개수)일 때  O(G * (V + E) log V) 복잡도를 가지게 된다. 약 10^10의 복잡도를 가지게 되어, 시간 안에 풀 수 없다.

 

2. 이 문제에서는 다익스트라 초기값이 여러 개 여도 된다. 

왜 그럴까? 이 문제에서 요구하는 것은 intensity가 최소가 되는 시작점(출입구)가 아니다. 어느 출입구든 상관없이 최소의 intensity로 산봉우리에 방문하기만 하면 된다.

 

A(출입구) -> 4 -> B(쉼터) -> 4 -> C(산봉우리)

D(출입구) -> 2 -> B(쉼터) -> 4 -> C(산봉우리)

 

A에서 출발하냐, D에서 출발하냐는 중요하지 않다. B까지 갈 때 최소 intensity가 2라는 것만 중요하다. 

--> 그래서 우리는 우선순위 큐를 초기화할 때 출발 노드를 여러 개 넣을 수 있다. 출발 노드를 여러 개 넣는 것은 거리가 0인 노드를 여러 개 넣는 것뿐이다. 따라서, 다익스트라를 1번 돌리는 것과 동일한 복잡도로 문제를 풀 수 있다. 

 

4️⃣ 코드

import heapq

def solution(n, paths, gates, summits):
    answer = []
    # 휴식 없이 이동해야 하는 시간 중 가장 긴 시간 -> intensity
    # 출입은 처음과 끝에 한 번씩 -> 산봉우리는 한 번만
    # intensity가 최소가 되는 등산코스
    
    gates = set(gates)
    summits = set(summits)

    INF = float('inf')
    intensities = [INF for i in range(n+1)]
    edges = [[] for i in range(n+1)]
    
    for p in paths:
        a,b,c = p
        edges[a].append((b,c))
        edges[b].append((a,c))
        
    heap = []
        
    for g in gates:
        intensities[g] = 0 # 출입구는 거리 0
        heapq.heappush(heap, (0,g))
        
        
    while heap:
        # 거리가 가까운 것부터 가면서 summits에 있는지 확인
        # summits에 있으면 거기까지 inten을 배열에 기록한다
        inten, node = heapq.heappop(heap)
        if (node in summits):
            answer.append((inten, node))
        else: 
            if (inten > intensities[node]):
                continue
            for newnode, newinten in edges[node]:
                if (newnode not in gates): 
                    newinten = max(inten, newinten)
                    if (newinten < intensities[newnode]):
                        intensities[newnode] = newinten
                        heapq.heappush(heap, (newinten, newnode))
 
    answer.sort()
    answer = [answer[0][1], answer[0][0]]
    return answer

 

 

+ 유사한 문제

https://www.acmicpc.net/problem/14221