[Programmers] P118669 등산코스 정하기

[Programmers] P118669 등산코스 정하기

Question

Language: Python

해당 문제를 보면 start - summit - start으로 사이클이 있는 것 처럼 보이지만, 사실은 start-summit만 정해지게 되면 돌아오는 길은 자동으로 정해지게 된다. 그래서, summit을 한번이라도 찍게되면 그 순간 해당 경로에 대해서는 탐색을 종료하면 된다.

그렇기 때문에 해당 문제는 하나의 start 점에 대해 각각의 노드에 대해 분석하는 dijkstra algorithm을 통한 접근을 고려하면 된다. 대신, 일반적으로 해당 노드까지의 거리를 변수로 설정하는 것이 아닌, 해당 노드까지 경로에서 edge cost가 가장 긴, 즉 intensity값을 변수를 삼는다.

특정 노드에 대한 탐색을 이어나가는 것을 결정하는 과정에서 intensity가 기존에 저장되어 있는 intensity보다 작으면 다음 탐색을 이어나가는 것이다.

for adj_vertex, weight in graph[vertex]:
    max_intensity=max(intensity,weight)
    #다음 노드에 대해 판별시, 저장된 intensity가 낮은 경우에 대해서만 탐색을 이어간다.
    if node_intensity[adj_vertex] > max_intensity:
        node_intensity[adj_vertex]=max_intensity
        heappush(heap,(node_intensity[adj_vertex],adj_vertex)) 

실수한 부분

처음에는 bfs를 이용하려고 하였으나, 이렇게 하게 되면 쉼터만 계속해서 이용하게 되는 cycle이 존재하게 되어 무한 루프가 발생한다.

이를 해결하기 위해 특정 노드까지 도달하는 과정에서의 intensity를 저장하므로써, 저장된 intensity보다 작은 경우에 대해서만 노드를 다시 반복하도록 지정하도록 변경하였다.

Solution

from heapq import heappush,heappop
from math import inf

def solution(n, paths, gates, summits):
    answer = []
    graph=[[] for _ in range(n+1)]
    heap=[]

    node_intensity=[inf]*(n+1)
    
    #노드 정보 파악
    node_info=[0]*(n+1)
    
    #출발지 정보
    for gate in gates:
        node_info[gate]=1
        heappush(heap,(0,gate))
        node_intensity[gate]=0
        
    #산봉우리 정보
    for summit in summits:
        node_info[summit]=2      
    #간선 정보 추가
    for v1,v2,cost in paths:
        graph[v1].append((v2,cost))
        graph[v2].append((v1,cost))
    
    while heap:
        intensity,vertex=heappop(heap)
        
        #산봉우리에서 나가는 간선이거나  해당 노드까지의 intensity가 더 긴 경우생략한다
        if node_info[vertex] == 2 or node_intensity[vertex] < intensity:
            continue
        
        for adj_vertex, weight in graph[vertex]:
            max_intensity=max(intensity,weight)
            #다음 노드에 대해 판별시, 저장된 intensity가 낮은 경우에 대해서만 탐색을 이어간다.
            if node_intensity[adj_vertex] > max_intensity:
                node_intensity[adj_vertex]=max_intensity
                heappush(heap,(node_intensity[adj_vertex],adj_vertex))   
    
    #모든 탐색이 완료되면, 최소 intensity, 최소 summit_index가 답이 된다.
    summits.sort()
    min_intensity=inf
    for summit in summits:
        if min_intensity > node_intensity[summit]:
            min_intensity=node_intensity[summit]
            answer=[summit,min_intensity]
    
    return answer