99클럽 코테 스터디 1일차 TIL + 달빛 여우

공부한 내용 본인의 언어로 정리하기

오늘은 백준 16118번 달빛 여우 문제를 풀며, 상태를 갖는 다익스트라 알고리즘을 공부했다.
기본적인 다익스트라 알고리즘은 하나의 최단 거리만을 저장하지만, 이 문제에서 늑대는 이동 시 두 가지 속도 상태(빠름, 느림)를 반복하므로 각 노드에 대해 두 개의 거리 정보를 저장해야 한다.

핵심은 다음과 같다:

• 여우는 평범한 다익스트라를 사용한다.
• 늑대는 "빠름 → 느림 → 빠름…"의 패턴을 따르므로, 각 상태에 따라 비용이 다르다.
  • 빠를 때는 거리의 절반(weight // 2)
  • 느릴 때는 거리의 두 배(weight * 2)
• 늑대의 다익스트라는 distance[node][0 or 1] 구조를 통해 상태 전환을 관리하며 진행된다.

또한, 정수 연산을 위해 모든 간선 거리를 2배 해주는 트릭도 배웠다.

 

작성 코드

# https://www.acmicpc.net/problem/16118
import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

def dijkstra_for_fox(start):
    pq = []
    distance = [INF] * n
    distance[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        cur_dist, cur_node = heapq.heappop(pq)

        if cur_dist > distance[cur_node]:
            continue

        for next_node, weight in graph[cur_node]:
            dist = cur_dist + weight
            if dist < distance[next_node]:
                distance[next_node] = dist
                heapq.heappush(pq, (dist, next_node))

    return distance

def dijkstra_for_wolf(start):
    pq = []
    distance = [[INF] * 2 for _ in range(n)]  # [빠름, 느림]
    distance[start][0] = 0  # 시작은 빠르게

    heapq.heappush(pq, (0, start, 0))  # 거리, 노드, 상태(0=빠름, 1=느림)

    while pq:
        cur_dist, cur_node, state = heapq.heappop(pq)

        if distance[cur_node][state] < cur_dist:
            continue

        for next_node, weight in graph[cur_node]:
            if state == 0:  # 다음은 느리게 감
                new_dist = cur_dist + weight // 2
                if new_dist < distance[next_node][1]:
                    distance[next_node][1] = new_dist
                    heapq.heappush(pq, (new_dist, next_node, 1))
            else:  # 다음은 빠르게 감
                new_dist = cur_dist + weight * 2
                if new_dist < distance[next_node][0]:
                    distance[next_node][0] = new_dist
                    heapq.heappush(pq, (new_dist, next_node, 0))

    return distance

# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b, d = map(int, input().split())
    d *= 2  # 정수 연산을 위해 거리 두 배로 저장
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))

fox_dist = dijkstra_for_fox(0)
wolf_dist = dijkstra_for_wolf(0)

# 결과: 여우가 더 빠른 경우만 카운트
cnt = 0

for i in range(n):
    if fox_dist[i] < wolf_dist[i][0] and  fox_dist[i] < wolf_dist[i][1]:
        cnt += 1
        
print(cnt)

---

오늘의 회고

• 문제 상황:
  처음엔 늑대도 일반 다익스트라처럼 단일 거리 배열을 써서 처리하려고 했는데, 상태 전환(빠름/느림)에 따라 최단 경로가 달라질 수 있다는 점을 간과했다.
• 어떤 시도를 했는지:
  상태별로 거리를 따로 저장하고, 우선순위 큐에 상태를 함께 넣어 다익스트라를 두 갈래로 나눴다.
• 어떻게 해결했는지:
  각 노드마다 [빠른 상태, 느린 상태] 두 가지 경우의 최단 거리를 관리하며 다익스트라를 돌렸다.
  상태 전환에 따른 거리 계산만 정확히 하면 로직 자체는 꽤 직관적이었다.
• 무엇을 새롭게 알았는지:
  다익스트라에서도 단순히 최소 거리만 저장하지 않고, 상황(상태, 방향 등)에 따라 멀티 상태 기반 거리 관리가 필요할 수 있다는 점을 새롭게 배웠다.
• 내일 학습할 것:
  • 다양한 응용 다익스트라 문제 더 풀어보기 (예: 타임머신, 파티 문제 등)
  • 상태 전이 그래프 이론 공부하기
  • 플로이드-워셜 알고리즘도 다시 복습 예정