PLOD

공부한 내용 본인의 언어로 정리하기오늘은 백준 16118번 달빛 여우 문제를 풀며, 상태를 갖는 다익스트라 알고리즘을 공부했다.기본적인 다익스트라 알고리즘은 하나의 최단 거리만을 저장하지만, 이 문제에서 늑대는 이동 시 두 가지 속도 상태(빠름, 느림)를 반복하므로 각 노드에 대해 두 개의 거리 정보를 저장해야 한다.핵심은 다음과 같다:여우는 평범한 다익스트라를 사용한다.늑대는 "빠름 → 느림 → 빠름…"의 패턴을 따르므로, 각 상태에 따라 비용이 다르다.빠를 때는 거리의 절반(weight // 2)느릴 때는 거리의 두 배(weight * 2)늑대의 다익스트라는 distance[node][0 or 1] 구조를 통해 상태 전환을 관리하며 진행된다.또한, 정수 연산을 위해 모든 간선 거리를 2배 해주는 트릭..