[Python] 2022 KAKAO TECH INTERNSHIP : 등산코스 정하기

2022 KAKAO TECH INTERNSHIP : 등산코스 정하기

문제 풀이

이 문제는 heap 자료 구조를 이용한 다익스트라(Dijkstra) 알고리즘을 이용해 푸는 문제이다.
heap을 사용하지 않고 구현하면, 매번 최단 거리가 가장 짧은 노드를 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야 한다.

heap이란?

• 우선순위 큐 기능을 구현하고자 할 때 사용되는 자료구조 중 하나
• 파이썬에서 힙 기능을 위해 heapq 라이브러리를 제공함
• 파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료됨

출발지에서 산봉우리를 도착할 때의 최소 intensity 값을 구하면 똑같은 경로로 출발지까지 다시 이동하면 되기 때문에 편도 경로만 고려하면 된다.

1. 출발지(출입구)들을 heap에 push 해주고 방문 기록을 해준다.

2. defaultdict(list) 형태 안에 연결된 노드와 가중치를 입력한다.

3. gates, summits를 해쉬화 하여 시간복잡도를 줄인다.(O(N) -> O(1))

• 이 작업을 하지 않는다면 시간 초과한다.

4. heap 안에 아무것도 없을 때까지 반복

   4-1. 현재 노드가 산봉우리거나 intensity가 기록된 intensity보다 더 클 경우 continue

   4-2. 다음 노드의 intensity가 기록된 intensity보다 작을 경우 기록하고, heap에 push 한다.

5. 기록한 노드에 따른 intensity를 바탕으로 intensity가 가장 작은 이동경로(출구)를 찾는다.

답

from collections import defaultdict
from heapq import heappush, heappop

def solution(n, paths, gates, summits):
    
    
    def get_min():
        hq = []
        visited = [10000001] * (n+1) 
        set_gates = set(gates) # 문제 풀이 3번
        for gate in set_gates: # 문제 풀이 1번
            heappush(hq, (0, gate))
            visited[gate] = 0
        
        while hq: # 문제 풀이 4번
            intensity, node = heappop(hq)
            # 산봉우리거나 intensity가 더 클 경우
            # 문제 풀이 4-1번.
            if node in set_summit or intensity > visited[node]: continue
            # 문제 풀이 4-2번
            for weight, next_node in graph[node]:
                next_intensity = max(weight, intensity)
                if next_intensity < visited[next_node]:
                    visited[next_node] = next_intensity
                    heappush(hq, (next_intensity, next_node))
                    
        min_intensity = [0, 10000001]    
        for summit in summits: # 문제 풀이 5번
            if min_intensity[1] > visited[summit]:
                min_intensity[0] = summit
                min_intensity[1] = visited[summit]
        
        return min_intensity
    
    summits.sort()
    # 문제 풀이 3번
    set_summit = set(summits) #sumiits 해쉬화하여 시간복잡도 줄임 
    graph = defaultdict(list)
    # 문제 풀이 2번
    for i,j,w in paths:
        graph[i].append((w,j))
        graph[j].append((w,i))
                
    
    return get_min()