작심 큰일 챌린지 - 달빛 여우 (파이썬)

새로 배운 개념이나 기술:
기존 다익스트라만 알고 있었는데 이렇게 상태에 따라 다르게 관리해주는 상태 기반 다익스트라 문제를 처음 풀어봐서 새로웠다. dp든 dijkstra든 상태에 따라 결과가 달라지는 문제는 원래 차수 + 1로 상태를 관리해주는 리스트를 운영해야 겠다고 생각했다.

또한 float와 int를 비교하는 과정에서 에러가 나지 않을까 걱정했는데 답은 맞았지만 안전하게 *2배를 해주는 것이 좋다는 피드백을 보고 안전한 코드를 작성하는 방법도 배운 것 같다.

마지막으로 0->1->0->1 이렇게 상태가 반복되는 것은 toggle(^)을 이용하면 된다는 것을 배웠다.

어려웠던 점과 해결 방법:
상태에 따라 바뀌는 최단 거리를 다루는 점 -> 1차원 거리 배열이 아니라 상태까지 포함한 2차원 최단 거리 배열을 만들었다.

 

접근 방법:

1. 입력 처리: 마을 수랑 길 정보 받고, 간선 거리는 처음부터 2배로 저장해. 왜냐면 늑대가 반으로 나눌 때 float 안 쓰고 정수로 계산해야 안전하거든
2. 여우 경로 계산: 이건 다들 아는 기본 다익스트라 그대로 쓰면 돼
3. 늑대 경로 계산: 여기가 핵심이야 → 늑대는 이동 상태(빠름/느림) 를 고려해서, 각 노드마다 [0, 1] 두 개의 최단 거리를 따로 저장해야 해
4. 최종 비교: 여우가 더 빠르게 도착한 마을만 세면 끝!

주의사항:

- 늑대는 같은 노드라도 상태에 따라 거리값이 다르기 때문에 거리 배열을 1차원이 아니라 2차원 리스트로 구성해야 해 (wolf_dist[node][state] 형태로 관리)
- 연산할 때 실수(float) 쓰면 오류 생기기 쉬우니까,간선 길이를 애초에 2배로 만들어두고 //2, *2로 안전하게 처리하자

import sys, heapq
input = sys.stdin.readline
def solution():
    n, m = map(int, input().split())
    # 시작 노드는 1, 늑대는 d/2 -> d*2 -> d/2 반복
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = map(int, input().split())
        graph[a].append((b, d))
        # 오솔길은 어떤 방향으로든 지나갈 수 있으며 -> 양방향
        graph[b].append((a, d))
    INF = float('inf')
    fdistance = [INF]*(n+1) # 여우가 간 거리
    wdistance = [[INF, INF] for _ in range(n+1)] # 늑대가 간 거리(상태 분리가 필요하므로 2차원으로 생성)
    # wdistance[i][0]: i번 노드를 짝수 깊이에 도착한 거리, wdistance[i][1]: i번 노드를 홀수 깊이에 도착한 거리
    def fdijkstra(start):
        fdistance[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        while q:
            dist, now = heapq.heappop(q)

            if dist > fdistance[now]:
                continue
            for nxt, ndist in graph[now]:
                cost = dist + ndist
                if cost < fdistance[nxt]:
                    fdistance[nxt] = cost
                    heapq.heappush(q, (cost, nxt))
        return fdistance[1:]
    def wdijkstra(start):
        wdistance[start][0] = 0
        q = []
        heapq.heappush(q, (0, start, 0))
        while q:
            dist, now, depth = heapq.heappop(q)
            parity = depth%2 # now 노드의 상태
            if dist > wdistance[now][parity]:
                continue
            for nxt, ndist in graph[now]:
                if parity == 0: # 짝수이면 2배 빨라지기
                    cost = dist+(ndist/2)
                else: # 홀수이면 2배 느려지기
                    cost = dist+(ndist*2)
                nxt_parity = (depth+1)%2 # 이동 후의 홀짝
                if cost < wdistance[nxt][nxt_parity]: # 이동 후의 상태로 갱신해야 함
                    wdistance[nxt][nxt_parity] = cost
                    heapq.heappush(q, (cost, nxt, depth+1))
        return [min(wdistance[i]) for i in range(1, n+1)]
    fdistance = fdijkstra(1)
    wdistance = wdijkstra(1)
    count = 0
    # print(f"fox: {fdistance}")
    # print(f"wolf: {wdistance}")
    for i in range(1, n): # i는 여우가 늑대보다 먼저 도락할 수 있는 노드
        if fdistance[i] < wdistance[i]:
            count += 1
    print(count)
solution()

 

아래는 정답 코드

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

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    c *= 2
    graph[a].append((b, c))
    graph[b].append((a, c))

INF = 800000000

# 여우
fox_shortcut = [INF] * (N + 1)
fox_shortcut[1] = 0
hq = [(0, 1)]

while hq:
    length, node = heappop(hq)
    if fox_shortcut[node] < length:
        continue
    for next_node, l in graph[node]:
        next_length = length + l
        if fox_shortcut[next_node] > next_length:
            fox_shortcut[next_node] = next_length
            heappush(hq, (next_length, next_node))

# 늑대
wolf_shortcut = [[INF, INF] for _ in range(N + 1)]
wolf_shortcut[1] = [0, INF]
hq = [(0, 0, 1)]  # (length, cnt, node)

while hq:
    length, cnt, node = heappop(hq)
    if wolf_shortcut[node][cnt] < length:
        continue
    ncnt = cnt ^ 1
    for next_node, l in graph[node]:
        if cnt == 0:
            l //= 2
        else:
            l *= 2
        next_length = length + l
        if wolf_shortcut[next_node][ncnt] > next_length:
            wolf_shortcut[next_node][ncnt] = next_length
            heappush(hq, (next_length, ncnt, next_node))

# 계산
ans = 0
for i in range(2, N + 1):
    if fox_shortcut[i] < min(wolf_shortcut[i]):
        ans += 1
print(ans)