백준 16118번: 달빛 여우 (Python)

접근

https://www.acmicpc.net/problem/16118

16118번: 달빛 여우

다익스트라 알고리즘에 조금 양념을 첨가한 문제였던 것 같습니다.

오솔길들이 있고 달빛 여우는 목적지까지 일반적인 다익스트라 알고리즘을 통해 최단거리로 이동하여 목적지에 도달합니다.

반면 달빛 늑대는 처음에는 2배의 속도, 그리고 그다음에는 절반의 속도로 번갈아가며 오솔길을 통과합니다. 이때 속도가 2배가 된다는 것은 걸리는 시간이 절반이 걸린다는 뜻이고, 반대도 그렇게 생각할 수 있습니다. 즉, 달릴 때에는 길이를 절반이라고 생각하고, 걸을 때에는 길이를 두배라고 생각해도 문제를 푸는데 문제가 없다는 뜻입니다.

늑대의 이동을 계산할 때에는 일반적인 1차원 배열로 계산하지 않고, N * 2 배열을 만들어 해당 위치에 도달했을 때, 뛰어서 왔는지 걸어서 왔는지에 따라 다른 위치에 걸린 시간을 저장해줍니다. 처음에 출발하는 위치에서는 무조건 달려서 출발하기 때문에 다익스트라 초기 위치도 달려나가는 쪽만 0으로 바꿔줍니다. 즉, d[1][1] = 0 으로 처음에 1의 위치에서 달려나가는 부분만 걸린 시간을 0으로 만들어주고, d[1][0] 이 의미하는 1번 위치에서 걸어서 출발하는 값은 INF 로 그대로 둡니다.

그리고 priority queue 에 넣는 값에도 해당 위치에서 달려야 하는지, 걸어야 하는지 정보를 포함해줍니다. 이를 이용해 탐색하면서, priority queue 에서 pop 된 값이 달리라고 한다면 push 할때 다음에는 걸으라고 표시하고, 반대로도 마찬가지 입니다.

코드

import sys
import heapq

input = sys.stdin.readline
INF = float("inf")

N, M = map(int, input().split(" "))
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, d = map(int, input().split(" "))
    graph[a].append((d, b))
    graph[b].append((d, a))


# 달빛 여우: 일반적인 다익스트라 알고리즘
def dijkstra_fox():
    d = [INF] * (N + 1)
    d[1] = 0
    pq = [(0, 1)]
    while pq:
        weight, now = heapq.heappop(pq)
        if d[now] < weight:
            continue
        for w, n in graph[now]:
            nw = weight + w
            if nw < d[n]:
                d[n] = nw
                heapq.heappush(pq, (nw, n))
    return d


# 달빛 늑대: 달리기/걷기에 따른 가중치를 준 다익스트라 알고리즘
def dijkstra_wolf():
    # (N + 1) * 2 배열로 초기화
    d = [[INF] * 2 for _ in range(N + 1)]
    # 1번 위치에서 달려서(1) 출발한다는 의미
    d[1][1] = 0
    pq = [(0, 1, 1)]
    while pq:
        weight, now, run = heapq.heappop(pq)
        if d[now][run] < weight:
            continue
        for w, n in graph[now]:
            # now 위치에서 달려야 한다면(run == 1)
            if run:
                # 다음 위치로 갈 때 거리가 절반이라고 계산
                nw = weight + w / 2
                if nw < d[n][0]:
                    d[n][0] = nw
                    # 다음 위치 n 에서는 걸어서 출발하도록 run == 0 전달
                    heapq.heappush(pq, (nw, n, 0))
            # now 위치에서 걸어야 한다면(run == 0)
            else:
                # 다음 위치로 갈 때 거리가 두배라고 계산
                nw = weight + w * 2
                if nw < d[n][1]:
                    d[n][1] = nw
                    # 다음 위치에서는 뛰어서 출발하도록 run == 1 전달
                    heapq.heappush(pq, (nw, n, 1))
    return d


fox_d = dijkstra_fox()
wolf_d = dijkstra_wolf()
cnt = 0
# 달빛 여우가 n번 그루터기에서 걸린 시간이 달빛 늑대가 걸린 시간 2개보다 작다면 카운트
for i in range(1, N + 1):
    if fox_d[i] < wolf_d[i][0] and fox_d[i] < wolf_d[i][1]:
        cnt += 1
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!