2022카카오인턴십: [Dijkstra] 등산코스 정하기[lv3]

문제

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

프로그래머스

 

접근방법

우선순위 큐를 활용한 다익스트라 알고리즘으로 풀이 + Greedy

 

[그리디 알고리즘을 위한 아이디어 도출해내기] : 가장 그럴듯 한 해를 구하는 것으로 최적해를 구할 수 있는 경우 

출발점에서 산봉우리를 올라갔다가 다시 돌아오는 것까지 고려하는 것은 복잡함,

-> 특정 산봉우리까지 편도 코스의 intensity(간선 최대값)를 우선순위 큐에 추가하는 것만으로도 정답도출 가능 

-> why? 돌아올 때도 같은 경로로 돌아오면 되니까 

 

[ 엣지케이스 검토하기 ]

intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

- summits.sort () 

코드

        

          

            

            

            

          
          
PYTHON
          
        
      from collections import defaultdict
from heapq import heappush, heappop

# 산봉우리까지 올라가는 단방향 intensity(경로최대값)의 최소값을 구하는 문제로 아이디어 구체화 

def solution(n, paths, gates, summits):
    # 산봉우리 오름차순 정렬
    summits.sort()
    graph = defaultdict(list) # 존재하지 않는 키로 참조시 []를 할당 
    
    # i:j 인접리스트 구현
    for i, j, w in paths:
        graph[i].append((w, j)) # i노드는 j와 w 가중치로 연결
        graph[j].append((w, i)) # j노드는 i와 w 가중치로 연결

    pq = []
    INF = float('inf') # 무한대값 or 1000001
    visited = [INF] * (n + 1) # 방문처리배열 (n번 노드를 인덱스로 취하기 위한 +1처리)
    
    for gate in gates: # 출입구 노드를 pq에 삽입 후 방문처리 
        heappush(pq, (0, gate))
        visited[gate] = 0

    while pq: # 큐가 빌 때까지
        intensity, node = heappop(pq) # 디큐로 시작 
        
        if intensity > visited[node] or node in summits: # 이미 방문한 or node가 산봉우리라면 continue
            continue # 탐색할 노드가 이미 산봉우리라면 인접노드를 계산할 필요가 없으므로 continue 

        for weight, next_node in graph[node]: # 그래프를 순회 -> key : [(w가중치,j인접노드),(w2,j2).....] 
            next_intensity = max(weight, intensity) #현재노드의 디큐로부터 뽑은intensity vs 인접노드 weight => intensit
            if next_intensity < visited[next_node]: # 방문처리용 : INF보다 작다면 Node까지의 intensity 최소값으로 갱신
                visited[next_node] = next_intensity # 우리의 목적은 Node까지의 intensity 최소값 (갱신로직)
                heappush(pq, (next_intensity, next_node)) # pq에 (intensity,노드) 추가 

    min_intensity = [0, INF]
    
    # summits의 intensity 최소값 구하기 
    # 엣지케이스:  여러 산봉우리가 같은 intensity를 가질 경우 가장 summit을 반환해야함 
    # => summits를 sort()로 정렬해주어야 
    ans = []
    for i in range(len(summits)):
        ans.append([summits[i],visited[summits[i]]]) # summit, w
    ans.sort(key=lambda x:x[1]) # instensity 최소값 순서로 정렬 
    return ans[0]