✅ 오늘의 학습 키워드
- 다익스트라 알고리즘 (Dijkstra Algorithm)
- 상태를 나누는 그래프 탐색
- 우선순위 큐 (heapq) 활용
✍️ 공부한 내용
오늘은 다익스트라 알고리즘을 복습하면서, 한 정점에서 다른 정점으로 가는 최단 거리를 구하는 방법에 대해 다시 정리했다. 특히, 이번 문제는 일반적인 다익스트라와 달리 이동 속도가 달라지는 두 개체(달빛 여우 vs 달빛 늑대)의 전략을 구현해야 해서 재미있었다.
달빛 늑대의 경우, 오솔길을 번갈아 빠르게/느리게 이동하기 때문에, 두 가지 상태(빠르게 이동 중 / 느리게 이동 중)로 나누어 다익스트라를 돌려야 했다.
🧠 오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
처음에는 달빛 늑대의 이동 전략을 단순하게 구현했다가, 상태 전환(빠름 → 느림 → 빠름…)을 고려하지 않아서 결과가 틀렸다.
어떻게 해결했는지
늑대의 이동 상태를 2차원 배열로 관리해서, 현재 상태에 따라 다음 상태를 전환하며 최소 시간을 업데이트하는 방식으로 다익스트라를 수정했다.
구체적으로는, wolf_dist[0][node]은 빠르게 도달한 경우, wolf_dist[1][node]는 느리게 도달한 경우를 의미하며, 힙에 상태까지 같이 넣어 탐색하도록 했다.
무엇을 새롭게 알았는지
상태가 다른 경우에도 다익스트라에서 두 개의 dist 배열(혹은 2차원 배열)을 쓰는 방식이 매우 유용하다는 것을 다시 느꼈다.
또한, 속도 비교가 필요한 문제에서는 cost를 통일(예: 2) 해서 소수 계산 없이 정수로 비교할 수 있게 만드는 것도 좋은 트릭이라는 것을 알게 되었다.
작성 코드
import heapq
import sys
input = sys.stdin.read
INF = sys.maxsize
def solve():
data = input().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
graph = [[] for _ in range(N + 1)]
for _ in range(M):
a = int(data[idx]); idx += 1
b = int(data[idx]); idx += 1
d = int(data[idx]); idx += 1
graph[a].append((b, d * 2))
graph[b].append((a, d * 2)) # 여우 기준으로 모두 *2 (늑대 처리 시 편하게 하기 위해)
# 여우의 최단거리 (일반적인 다익스트라)
fox_dist = [INF] * (N + 1)
fox_dist[1] = 0
heap = [(0, 1)]
while heap:
time, now = heapq.heappop(heap)
if fox_dist[now] < time:
continue
for nxt, cost in graph[now]:
if fox_dist[nxt] > time + cost:
fox_dist[nxt] = time + cost
heapq.heappush(heap, (time + cost, nxt))
# 늑대의 최단거리 (두 가지 상태: 빠르게 vs 느리게)
wolf_dist = [[INF] * (N + 1) for _ in range(2)] # 0: 빠르게, 1: 느리게
wolf_dist[0][1] = 0
heap = [(0, 1, 0)] # (time, node, state)
while heap:
time, now, state = heapq.heappop(heap)
if wolf_dist[state][now] < time:
continue
for nxt, cost in graph[now]:
if state == 0: # 빠르게: 시간 절반
new_time = time + cost // 2
if wolf_dist[1][nxt] > new_time:
wolf_dist[1][nxt] = new_time
heapq.heappush(heap, (new_time, nxt, 1))
else: # 느리게: 시간 두 배
new_time = time + cost * 2
if wolf_dist[0][nxt] > new_time:
wolf_dist[0][nxt] = new_time
heapq.heappush(heap, (new_time, nxt, 0))
# 비교
result = 0
for i in range(2, N + 1):
if fox_dist[i] < min(wolf_dist[0][i], wolf_dist[1][i]):
result += 1
print(result)
solve()#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
