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

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

프로그래머스

풀이 방법

풀지 못하여 다른 분들의 풀이를 참고했다.

다익스트라를 변형한 문제였다.

이 문제의 핵심은 편도만 경로만 구하면 되는 것이다.

또 다익스트라를 적용하여 값들을 업데이트할 때 max(이전 노드의 값, 이전 노드와 현재 노드의 가중치)를 사용해야 한다.

 

import heapq
def solution(n, paths, gates, summits):
    graph = [[] for _ in range(n+1)] ## 그래프 생성
    distance = [987654321] * (n+1) ## gate에서 갈 수 있는 최소 intensity 배열
    for a, b, w in paths: ## 그래프 초기화 
        graph[a].append([b, w])
        graph[b].append([a, w])    
    is_summit = [False] * (n + 1)
    for summit in summits:
        is_summit[summit] = True

    is_gate = [False] * (n + 1)
    for gate in gates:
        is_gate[gate] = True
    def get_min_intensity():
        q = []        
        for gate in gates: ## 게이트 추가            
            heapq.heappush(q, [0, gate])
            distance[gate] = 0
        while q:
            intensity, node = heapq.heappop(q)            
            if distance[node] < intensity or is_summit[node]:
                continue                                
            for next_node, w in graph[node]:
                if not is_gate[next_node]: ## 서로 다른 입구 경로에 포함 불가                     
                    new_intensity = max(w, intensity) ## 다음 intensity 값 계산                
                    if (distance[next_node] > new_intensity): ## intensity 값이 낮은 게 있으면 추가 
                        distance[next_node] = new_intensity
                        heapq.heappush(q, [new_intensity, next_node])
        
    answer = []   
    get_min_intensity()
    min_intensity = 987654321
    min_num = 0   
    summits.sort()
    for i in summits:
        if min_intensity > distance[i]:
            min_intensity = distance[i]
            min_num = i
    answer.append(min_num)
    answer.append(min_intensity)    
    return answer

다음에 적용할 것

• 그래프를 무조건 모든 배열을 만들어 배열로 하지 말고(연결 안 된 건 -1로 설정) append 함수를 사용해서 연결된 간선만 저장하도록 하자.
• 시간 단축을 위해 가능한 리스트를 탐색하는 것은 배열로 미리 만들어 놓자 ex) if i in summits 대신 is_summits 배열을 만듦  
• 문제에 정렬이 되었다고 조건이 없으면 정렬하기 ex) summits.sort() 예시는 정렬되어 있는데 테스트 케이스 안된 것 있음.
• gate들을 동시에 우선순위 큐에 넣고 진행 가능한지 판단해 보기