[BOJ] 16118. 달빛여우 (🥇, 다익스트라)

🔗

풀이

여우와 늑대가 각각의 그루터기에 최단 시간으로 도착하고 도착한 시간들 중에서 여우가 늑대보다 빨리 도착할 수 있는 그루터기의 개수를 구하는 문제이다. 그루터기를 하나의 정점으로 생각하고 여우와 늑대가 출발하는 지점이 1이라면 1에서부터 다른 정점까지의 최단거리를 구하면 된다. 다익스트라 알고리즘을 사용하여 풀이했다.

여우의 이동 속도는 항상 일정하다고 했으므로 일반적인 다익스트라 풀이로 해결할 수 있었다. 하지만 늑대의 경우는 한 번은 2배의 속도로, 그 다음은 1/2속도로 이동하는 차이가 있었다. 이 말은 A에서 B라는 정점으로 1회차에 방문할 때는 2배속으로 방문하게 되지만, 2회차에 방문할 때는 1/2속도로 더 느리게 방문하게 될 것이라는 말이 된다.

하지만 그렇다고 해서 단순히 더 늦게 방문하게 되는 경우를 고려하지 않으면 위의 그래프에서 제대로 된 값을 구할 수 없게 된다. 정점 2에 방문할 수 있는 경우의 수는 1->2와 1->3->2 두 가지가 있을 수 있다. 다익스트라는 항상 최단거리부터 구해나가기 때문에 출발점과 연결되어 있는 경우(1->2)와 그 다음 최단거리의 정점에서 연결된 정점에서 구해지는 경우(1->3->2)가 있을 수 있기 때문이다. 1->2의 경우 1회차이기 때문에 2배의 속도로 이동해서 1.5의 이동거리를 갖게 된다. 1->3->2는 2회차이기 때문에 1->3은 1이지만 3->2는 1/2속도가 되어 4이므로 합쳐서 5가 된다. 이미 1회차의 이동으로 1.5만에 이동할 수 있는데, 정점2까지 가는데 5가 걸리는 속도를 굳이 저장할 필요가 있을까 싶었다.

하지만 문제는 정점4까지 이동하는 거리를 구할 때 생겼다. 1 3 2로 2회 이동한 경우는 2->4로 이동할 때 3회차가 되어 4의 절반인 2만큼 이동하게 된다. 하지만 1 2로 이동한 경우는 2->4의 이동이 3회차가 되어 4의 2배인 8만큼 이동하게 된다.

결국 각각의 정점에 홀수/짝수 회차에 방문했을 때 걸리는 각각의 최단시간을 모두 저장해야 한다. 2개의 정보를 저장해야 하기 때문에 최단거리를 저장하는 배열을 2차원으로 구현했다.

문제 사항

5 5
1 2 1
2 3 1
1 3 1
1 4 1
4 5 10000

위의 논리대로 풀이했지만 57%쯤에서 에러가 발생했다. 질문 게시판에서 위의 반례를 찾았다. 문제는 출발점으로 다시 되돌아올 수도 있다는 사항을 고려하지 않았던 점이었다. 출발점에서 이동하는 경우는 0회차에 해당한다. 다른 정점에 방문했다가 다시 돌아오는 경우를 고려해줘야 했는데 이걸 초기화할 때 미리 0으로 다해서 재방문이 불가능하게 했던 것이다. 그렇게 되면 위의 반례에서 1->3->1->4와 같이 방문할 수가 없게 되고, 4->5가 짝수 회차에 당첨되어 2만 시간이 넘게 걸리게 된다.

import sys
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline

# 늑대의 최단거리 구하기
def move_wolf(n, graph):
    dist = [[1e9, 1e9] for _ in range(n+1)]
    dist[1][0] = 0

    pq = [(0, 1, 0)]
    while pq:
        w, i, v = heappop(pq)
        if dist[i][v] != w:
            continue
        
        if v == 0:
            for j, _w in graph[i]:
                cost = w+_w/2
                if dist[j][1] > cost:
                    heappush(pq, (cost, j, 1))
                    dist[j][1] = cost
        else:
            for j, _w in graph[i]:
                cost = w + _w*2
                if dist[j][0] > cost:
                    heappush(pq, (cost, j, 0))
                    dist[j][0] = cost
    return list(map(min, dist[1:]))

# 여우의 최단거리 구하기
def move_fox(n, graph):
    dist = [1e9]*(n+1)
    dist[1] = 0

    pq = [(0, 1)]
    while pq:
        w, i = heappop(pq)
        if dist[i] != w:
            continue

        for j, _w in graph[i]:
            cost = w+_w
            if dist[j] > cost:
                dist[j] = cost
                heappush(pq, (cost, j))

    return dist[1:]

n, m = map(int, input().strip().split())
graph = defaultdict(list)
for _ in range(m):
    a, b, d = map(int, input().strip().split())
    graph[a].append([b, d])
    graph[b].append([a, d])

answer = 0
wolf, fox = move_wolf(n, graph), move_fox(n, graph)
for i in range(n):
    if fox[i] < wolf[i]:
        answer += 1
print(answer)