BOJ 16118. 달빛 여우 (Python) / 다익스트라

🔎 BOJ 16118. 달빛 여우 (Gold 1)

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

16118번: 달빛 여우

💡 SOL

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

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

# 여우 (정속)
v_fox = [float('inf')] * (N + 1)
v_fox[1] = 0
q = [(0, 1)]   # (cost, node)
while q:
    cost, s = heappop(q)
    if cost > v_fox[s]: continue
    for e, d in arr[s]:
        new_cost = cost + d
        if v_fox[e] > new_cost:
            heappush(q, (new_cost, e))
            v_fox[e] = new_cost

# 늑대 (변속)
v_wolf = [[float('inf'), float('inf')] for _ in range(N + 1)]   # [False일때, True일때]
q = [(0, 1, True)]    # (cost, node, t:가속/f:감속)
v_wolf[1][0] = 0
while q:
    cost, s, fast = heappop(q)
    if cost > v_wolf[s][not fast]: continue
    for e, d in arr[s]:
        if fast:
            new_cost = cost + (d / 2)
        else:
            new_cost = cost + (d * 2)
        if v_wolf[e][fast] > new_cost:
            v_wolf[e][fast] = new_cost
            heappush(q, (new_cost, e, not fast))

cnt = 0
for i in range(2, N + 1):
    if v_fox[i] < min(v_wolf[i]):
        cnt += 1
print(cnt)

💭 TIL

# 위 코드 중 일부 발췌
v_fox = [float('inf')] * (N + 1)
v_fox[1] = 0
q = [(0, 1)]   # (cost, node)
while q:
    cost, s = heappop(q)

    # q에서 node를 꺼내 쓸 때 최신화된 visited(=v)에 저장된 가중치의 최소값으로 필터링해주면
    # 똑같은 node를 여러 번 탐색하는 상황을 걸러낼 수 있다.
    if cost > v_fox[s]: continue

    for e, d in arr[s]:
        new_cost = cost + d
        if v_fox[e] > new_cost:

            # 같은 node가 다른 가중치를 가지고 q에 여러 번 추가될 수 있음
            heappush(q, (new_cost, e))

            v_fox[e] = new_cost

시간 초과때문에 고생했던 문제라 기록해둔다. (여전히 pypy로는 통과 안 됨)

dfs/bfs, 다익스트라 문제 많이 풀었지만 이 문제 시간 초과때문에 효율성에 대해 많이 고민해보게 되었다. 오히려 좋아 ^^ㅠ..

 

현재 위치에서 가능한 다음 위치를 찾으며 탐색할 때,

예를 들어 가중치 10을 가지는 다음 노드 2와 가중치 5를 가지는 다음 노드 2가 q에 순차적으로 들어온 상태라면

(최솟값을 찾는다는 가정 하에) 가중치 10인 노드 2는 다음 현재 위치로 고려하지 않아도 된다.

어차피 가중치 5짜리 노드 2를 탐색하면 되기 때문에!

따라서 현재 위치인 s를 뽑았을 때, 최신화된 visited(=v)에 저장된 가중치 값보다 크다면 그냥 pass 해버려도 좋다.

cost, s = heappop(q)

if cost > v_fox[s]: continue

 

해당 코드를 빼도 정답에 영향은 없지만 시간 제한이 중요한 문제에서는 필요하겠다..

가중치를 갖는 그래프 문제에서 범용적으로 써먹을 수 있을 것 같다.