다익스트라 알고리즘(Dijkstra Algorithm) 정리

👉 1. 다익스트라란?

가중치가 있는 그래프에서 하나의 출발점으로부터 모든 노드까지의 최단 거리를 구하는 알고리즘

• BFS와 비슷하지만, 가중치가 존재.
• Greedy(탐욕적 방법)을 이용해 가장 가까운 노드부터 하나씩 확정.
• 항상 현재까지 최소 거리를 기준으로 이동.

👉 2. 기본 작동 원리

1. 출발점 거리를 0으로 설정하고, 나머지 노드들은 무한대로 설정한다.
2. 가장 짧은 거리를 가진 노드를 선택한다.
3. 그 노드를 거쳐 다른 노드로 가는 거리를 계산하고, 더 짧으면 업데이트한다.
4. 모든 노드를 방문할 때까지 반복한다.

👉 3. 핵심 자료구조

🔥 코드 예시

import heapq

dp = [float('inf')] * s
dp[0] = 0
pq = []
heapq.heappush(pq, (0, 0))

• dp[pos]: 현재 위치 pos까지의 최소 비용(거리) 저장
• (거리, 위치)를 우선순위 큐에 저장 → 가장 가까운 위치부터 탐색

📊 다익스트라 흐름 시각화

초기 상태:

반복 과정:

• 0에서 출발하여 가능한 이동을 탐색
• 이동 가능한 위치는 거리 갱신
• 가장 가까운 노드를 선택해 다음 이동

📈 최종 목표

특정 값 m을 만들기 위해 필요한 최소 연산 횟수 구하기

print(dp[m % s] + m // s)

• m % s 위치까지 최소 연산 횟수를 구하고
• 몫 m // s를 더해 최종 연산 횟수 계산

🧩 전체 다이어그램

flowchart TD
    Start((출발점 0))
    Start --> A[0에서 이동할 수 있는 모든 위치 계산]
    A --> B{우선순위 큐에 삽입}
    B --> C[가장 가까운 위치 pop]
    C --> D{목표 도달 여부}
    D -- No --> A
    D -- Yes --> E[최소 거리 출력]

🛠 추가 팁

• heapq는 (거리, 위치) 순으로 거리 기준 최소 힙으로 동작
• 가중치는 음수가 없어야 정확하게 작동 (음수 있으면 벨만-포드 알고리즘 사용)

🔥 요약