99클럽 코테 스터디 11일차 TIL - 알고리즘의 원리를 정확히 알고있기

문제 - 등산코스 정하기 문제링크

문제 설명

산이 있고 산에는 지점들이 있습니다. 지점은 여러 개의 출발지와 여러 개의 정상, 그리고 일반 지점들이 있습니다.
출발지에서 시작해서 정상을 찍고 다시 원래 출발지로 돌아오는 경로가 있을 때, 해당 경로는 시작 출발지와 끝 출발지는 같고, 중간에 다른 출발지를 거치지 않고, 정상은 무조건 한번만 거쳐야 합니다.
이때, 위 조건을 만족하는 모든 경로 각각에서 각 지점을 건너는데 걸리는 시간 중 가장 긴 시간이 있을텐데 이를 intensity라 하고, 모든 경로를 통틀어 최소 intensity를 구하는 문제입니다.

 

풀이 과정

처음에는 같은 지점을 여러번 반복해서 방문할 수 있으므로, 비트마스킹을 이용헤서 중복 경로 체크를 해야 하는 줄 알았습니다. 하지만 이전에 방문한 지점들은 이미 intensity에 반영이 된 상태이기 때문에 굳이 방문했던 지점을 다시 갈 필요가 없어서 비트마스킹은 사용하지 않았고 지점 개수가 5만개까지 되기 때문에 사용할 수 없었습니다.
 
이후에는 gates와 summits 각각에 대해 다익스트라를 진행해서 각 gate에 대해 모든 summit에 도달하는 최소 intensity를 구하고 다시 각 summit에 대해 최소 intensity를 구해서 둘 중 가장 작은 값의 gate와 summit를 구하면 되겠다고 생각했습니다.
 
하지만 더 생각해보니 어차피 intensity가 최소인 경로로 출발지에서 정상에 도달하고, 방문한 지점을 다시 방문해도 되므로 정상에서 출발지로 같은 경로로 이동하면 되기 때문에 모든 gate->모든 summit까지만 다익스트라로 최소 intensity를 구하면 되겠다 라고 생각했습니다.
 
이때 제가 실수를 합니다. 그건 바로 다익스트라를 최대힙으로 구현한 점입니다. 최대힙으로 구현하게 되면, 힙에서 해당 지점에 대해 갈 수 있는 최대 intensity가 pop되기 때문에 만약 힙에 더 작은 intensity가 있었다면 이후에 pop될 때 다시 모든 지점에 대해 갱신하는 과정을 거쳐야 해서 더 시간이 오래 걸립니다.
 
아래는 최대힙으로 작성한 코드입니다.

from collections import defaultdict, deque
import heapq

MAX_NUM = 0x3f3f3f3f

def solution(n, paths, gates, summits):
    check_gate = set(gates)
    check_summit = set(summits)

    graph = defaultdict(list)
    for path in paths:
        u, v, w = path
        graph[u].append((v, w))
        graph[v].append((u, w))

    summits.sort()

    pq = []
    dist = [MAX_NUM] * (n + 1)
    
    min_intensity = float('inf')
    min_summit = float('inf')
    
    for gate in gates:
        dist[gate] = 0
        heapq.heappush(pq, (0, gate))

    while pq:
        d, pos = heapq.heappop(pq)
        
        # 해당 경로 비용이 더 나가면 패스
        if dist[pos] < -d:
            continue

        # 산봉우리 도착이면 패스
        if pos in check_summit:
            if min_intensity > -d or (min_intensity == -d and min_summit > pos):
                min_intensity = -d
                min_summit = pos
            continue

        for next, W in graph[pos]:
            # 게이트면 패스
            if next in check_gate:
                continue

            # 값이 더 작으면 거리 갱신하고 넣기
            max_intensity_in_path = max(-d, W)
            if dist[next] > max_intensity_in_path:
                dist[next] = max_intensity_in_path
                heapq.heappush(pq, (-max_intensity_in_path, next))

    return [min_summit, min_intensity]

 
그런데 제가 최대힙으로 작성한 이유가 있습니다. 그건 바로 예전에 c++로 해당 문제를 풀었을 때 최대힙으로 작성했고 c++는 매우 빠르기 때문에 별 무리 없이 통과해서 이때도 마찬가지로 최대힙을 사용했던 것입니다.
 
그러나 파이썬은 c++에 비해 매우 느렸고, gates와 summits을 set을 사용해서 체크해주는 최적화를 거쳤음에도 2개의 테스트케이스에 대해 시간초과가 발생했습니다.  

 
이후 정답코드를 확인해보니 최소힙으로 푸는걸 확인했고, 다익스트라가 최단거리를 빠르게 찾는 이유를 잊고 있었다는걸 깨달았습니다.
이후에는 최소힙으로 변경한 후 테스트케이스를 모두 통과하였습니다.

from collections import defaultdict, deque
import heapq

MAX_NUM = 0x3f3f3f3f

def solution(n, paths, gates, summits):
    check_gate = set(gates)
    check_summit = set(summits)

    graph = defaultdict(list)
    for path in paths:
        u, v, w = path
        graph[u].append((v, w))
        graph[v].append((u, w))

    summits.sort()

    pq = []
    dist = [MAX_NUM] * (n + 1)
    
    min_intensity = float('inf')
    min_summit = float('inf')
    
    for gate in gates:
        dist[gate] = 0
        heapq.heappush(pq, (0, gate))

    while pq:
        d, pos = heapq.heappop(pq)

        # 해당 경로 비용이 더 나가면 패스
        if dist[pos] < d:
            continue

        # 산봉우리 도착이면 패스
        if pos in check_summit:
            if min_intensity >= d and min_summit > pos:
                min_intensity = d
                min_summit = pos
            continue

        for next, W in graph[pos]:
            # 게이트면 패스
            if next in check_gate:
                continue

            # 값이 더 작으면 거리 갱신하고 넣기
            max_intensity_in_path = max(d, W)
            if dist[next] > max_intensity_in_path:
                dist[next] = max_intensity_in_path
                heapq.heappush(pq, (max_intensity_in_path, next))

    return [min_summit, min_intensity]

 

총평

다익스트라 알고리즘은 최단거리만 구할 수 있는게 아니다. 다익스트라는 일종의 인터페이스이고 그 안의 아이템들은 해당 노드까지의 최단거리일 수도 있고, 해당 노드까지의 최저, 최대 가중치 등 문제에서 구해야 하는 무엇이든 될 수 있다. 다만 가장 작은 아이템을 뽑아내어 진행한다는 점만 지키면 된다.
언어에 따라 같은 로직인데 한쪽은 정답이고 한쪽은 시간초과가 날 수 있다.