[프로그래머스] 2022 KAKAO TECH INTERNSHIP/등산코스 정하기/파이썬/python

💡 solutions  

💬 heap 자료 구조 사용, 각 출입구들을 노드로 넣고 다익스트라 알고리즘 탐색

💬 1. 산봉우리는 한 개만 지나야 하므로 탐색 노드가 산봉우리인 경우 탐색 중단

💬 2. 해당 노드를 지났던 기존 intensity(dist[node])가 현재의 intensity 보다 작은 경우는 이미 더 작은 intensity로 해당 노드를 지날 수 있다는 의미이므로 탐색 중단하도록 조건 처리

💬 각 노드의 intensity를 저장하는 dist 배열에서 값을 업데이트 할 때는 최대 intensity (현재 intensity, 다음 노드의 intensity 중 큰 값)로 저장한다.

💬 산봉우리들을 비교하여 가장 작은 intensity를 갖는 경우를 답으로 반환한다. 단, intensity가 동일한 봉우리들이 여러 개인 경우 봉우리 번호가 낮은 것을 답으로 반환한다. 

 

👨‍💻 code  

import heapq

def solution(n, paths, gates, summits):
    hq = []
    INF = float('inf')
    dist = [INF] * (n+1)
    answer = [0, INF]
    summits_set = set(summits)
    summits.sort()

    # 인접 배열 만들기
    adj = [[] for _ in range(n+1)]
    for path in paths:
        i, j, w = path
        adj[i].append((w, j))
        adj[j].append((w, i))

    # 모든 출입구를 정점으로 넣고, 다익스트라 알고리즘 탐색
    for gate in gates:
        heapq.heappush(hq, (0, gate))
        dist[gate] = 0

    while hq:
        intensity, node = heapq.heappop(hq)
        if intensity > dist[node] or node in summits_set:
            continue
        for next_intensity, next_node in adj[node]:
            if intensity <= next_intensity and dist[next_node] > next_intensity:
                dist[next_node] = next_intensity
                heapq.heappush(hq, (next_intensity, next_node))
            elif intensity > next_intensity and dist[next_node] > intensity:
                dist[next_node] = intensity
                heapq.heappush(hq, (intensity, next_node))

    # 후보가 되는 등산 코스가 여러 개라면 산봉우리 번호 가장 작은 것이 정답
    for summit in summits:
        if dist[summit] < answer[1]:
            answer[0] = summit
            answer[1] = dist[summit]
    return answer

 

 

📌 problem  

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

프로그래머스