다익스트라 알고리즘

낚시하는 곰·2025년 3월 30일

algorithm jungle

krafton jungle

목록 보기

28/52

다익스트라 알고리즘의 거리 갱신 로직 쉽게 풀기

먼저 비유부터 들어보자

너가 어떤 도시(A)에서 다른 도시들로 여행을 가고 있다고 상상해봐.
그리고 너는 가장 빠른 길을 찾고 싶어.

이때 "어떤 도시에 가는 데 걸리는 최단 시간"을 메모지에 적고 다닌다고 생각해보자.

단계별 설명

1단계. 처음엔 모든 도시는 얼마나 걸릴지 몰라

그래서 메모지에 이렇게 적혀 있어:
- A (시작 도시): 0분
- B: 무한대
- C: 무한대
- D: 무한대
(처음엔 다른 도시까지 얼마나 걸리는지 모르니까 '무한대'로 적어둠)

2단계. A에서 갈 수 있는 도시들을 확인해봐

예를 들어 A에서 B까지 3분 걸린다고 하자.
그럼 메모지를 이렇게 고쳐:
- B: min(무한대, 0 + 3) → 3분으로 갱신
A에서 C까지는 5분이면 갈 수 있다면?
- C: min(무한대, 0 + 5) → 5분으로 갱신

3단계. 이제 메모지를 다시 보고, 가장 시간이 적은 도시(B)를 방문

지금까지는:
- B: 3분
- C: 5분
- D: 무한대
그럼 B를 다음에 방문해.
그리고 B에서 연결된 도시가 있다면 그 도시들까지 걸리는 시간을 계산해봐.
예를 들어 B에서 C로 1분 걸린다면?
- C: min(5, 3 + 1) → 4분으로 갱신

예를 들어, B에서 D로 가는 시간이 10분이고,
현재 메모지에 D까지의 시간은 7분이라고 적혀 있다면?

계산된 값: 3(B까지 걸린 시간) + 10 = 13

메모지에 있는 값: 7
→ 13 > 7이므로 갱신하지 않음 (더 느린 길이기 때문)

4단계. 계속 이걸 반복해

메모지에 적힌 최단 시간은 계속 갱신돼.
이미 적혀있는 시간보다 더 빠르게 갈 수 있는 방법이 생기면 값을 바꾸는 거야.
그리고 항상 지금까지 가장 빠르게 갈 수 있는 도시부터 방문해.

함수명

함수명	설명
`dijkstra(start)`	`start` 정점에서 시작하는 다익스트라 함수
`add_edge(u, v, w)`	정점 `u`에서 정점 `v`로 가는 가중치 `w`의 간선 추가 (필요한 경우)
`initialize()`	거리 배열과 방문 배열 초기화

주요 변수명

변수명	의미
`graph`	인접 리스트 형태의 그래프 (예: `graph[u] = [(v, w), (x, y)]`)
`distance`	각 노드까지의 최단 거리 저장 배열 (초기값 무한대)
`visited`	해당 노드를 이미 방문했는지 여부 확인용 (불리언 배열)
`pq` 또는 `heap`	우선순위 큐 (heapq 사용 시)
`current` 또는 `cur_node`	현재 탐색 중인 노드
`cur_dist`	현재 노드까지의 거리
`next_node`	인접 노드
`weight` 또는 `edge_cost`	현재 간선을 통한 이동 비용

구현

import sys, heapq

INF = float("inf")

class answer:
    def __init__(self):
        self.n = int(sys.stdin.readline())
        self.m = int(sys.stdin.readline())
        self.pq = []


    def build_graph(self):        
        self.graph = [[] for _ in range(self.n + 1)]
        self.distance = [INF for _ in range(self.n + 1)]


    def add_edge(self):
        for _ in range(self.m):
            u, v, cost = map(int, sys.stdin.readline().split())
            self.graph[u].append([cost, v])


    def init_pq(self):
        self.start, self.end = map(int, sys.stdin.readline().split())
        self.distance[self.start] = 0

        heapq.heappush(self.pq, [0, self.start]) 


    def dijkstra(self):
        while len(self.pq) > 0:
            pop_dt = heapq.heappop(self.pq)
            current = pop_dt[1]
            cur_dist = pop_dt[0]

            if self.distance[current] < cur_dist:
                continue

            for i in self.graph[current]:
                edge_cost = i[0]
                next_node = i[1]

                new_dist = cur_dist + edge_cost
                if self.distance[next_node] > new_dist:
                    self.distance[next_node] = new_dist
                    heapq.heappush(self.pq, [new_dist, next_node])

        print(self.distance[self.end])

ans = answer()
ans.build_graph()
ans.add_edge()
ans.init_pq()
ans.dijkstra()

`seen` vs `visited`의 차이점

1. `seen`

말 그대로 "한 번이라도 본 적 있는 노드"를 의미해.
우선순위 큐에서 꺼낸 다음에 확인해서 중복 처리를 피할 때 사용해.
다익스트라 알고리즘에서는 최소 비용으로 확정된 노드만 추가해.

2. `visited`

보통 BFS/DFS에서 사용돼.
큐에 넣는 순간 visited 표시를 해버려. 다시 큐에 들어가는 걸 막기 위해서야.
하나의 노드를 한 번만 방문하도록 강제할 때 쓰여.

🌟 예시로 비교해보자

BFS에서의 `visited`

queue = deque([start])
visited = set([start])  # 큐에 넣는 순간 visited로 처리

while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

큐에 넣는 순간 visited 처리!
같은 노드를 큐에 중복으로 넣는 걸 막는 역할.

다익스트라에서의 `seen`

heap = [(0, start)]
seen = set()

while heap:
    cost, node = heappop(heap)
    if node in seen:  # 이미 최소 비용으로 처리한 적 있음
        continue
    seen.add(node)

    for neighbor, weight in graph[node]:
        heappush(heap, (cost + weight, neighbor))

꺼낸 다음에 seen 확인!
이유: 더 짧은 경로가 있을 수 있으므로, 확정된 비용일 때만 처리해야 돼.

🤔 왜 다익스트라는 큐에 넣을 때가 아니라 꺼낼 때 체크할까?

다익스트라는 "최단 거리"를 보장하는 알고리즘이기 때문에, 같은 노드가 여러 번 우선순위 큐에 들어갈 수 있어. 이 중 가장 짧은 비용으로 도달한 경우만 유효하기 때문에, 큐에서 꺼낼 때 그 노드가 이전에 처리되었는지를 seen으로 확인하는 거야.

만약 큐에 넣을 때 visited 처리를 해버리면, 더 짧은 경로가 나중에 발견되어도 무시돼버릴 수 있어서 최단 거리 보장이 깨지게 돼. 따라서 다익스트라는 꺼낼 때 처리하는 게 핵심이야.

⚠ 예외: A* 알고리즘이나 Dijkstra 변형에서 `visited`를 큐에 넣을 때 처리하는 경우

일부 A* 알고리즘이나 실용적인 최적화에서는 visited를 큐에 넣을 때 처리하기도 해. 대신 이때는 다음 조건을 추가해야 해:

큐에 들어가는 노드는 항상 "더 짧은 비용"을 보장하도록 갱신되어야 함
이미 더 좋은 경로로 방문했던 노드는 다시 큐에 안 들어가도록 따로 관리

즉, 이 방식은 추가적인 비용 비교나 조건이 붙어야 안전하게 동작할 수 있어. 일반적인 다익스트라에서는 seen을 꺼낸 다음에 처리하는 것이 기본이자 안전한 방식이야.

정리

상황	변수 이름	언제 체크?	목적
BFS/DFS	`visited`	큐에 넣기 전에	중복 방문 방지
다익스트라	`seen`	큐에서 꺼낸 후	최소 비용만 확정 처리

`set()`이 방문 여부를 체크하는 원리

1. `set`은 중복을 허용하지 않는 자료구조야.

예를 들어 seen.add('A')를 하면 A가 들어가.
이후 if 'A' in seen:을 하면 → True가 나와.
하지만 또다시 seen.add('A')를 해도, A는 중복으로 추가되지 않아.

즉, 한 번 추가한 값은 다시 들어가지 않음 → 이걸 이용해서 "이미 방문한 적 있니?" 를 체크할 수 있는 거야.

다익스트라에서의 흐름으로 설명해볼게

seen = set()
...
_, node = heappop(heap)

if node in seen:
    continue  # 이미 처리한 적 있으면 무시

seen.add(node)  # 이제 이 노드는 처리한 것으로 기록

흐름 요약:

heap에서 꺼낸 노드가 seen에 있는지 확인
있으면 → 이미 처리한 거니까 무시 (continue)
없으면 → 처음 방문한 거니까 seen.add(node)로 기록

왜 리스트나 딕셔너리가 아니라 `set`을 쓰는 걸까?

시간 복잡도 차이 때문이야.
- in 연산: 리스트는 O(n), set은 O(1) (평균)
- 빠르게 확인하고, 빠르게 추가할 수 있는 게 중요하니까 set이 최적이야.

왜 힙큐를 사용할까?

궁금했던 점
"큐에서 노드를 꺼냈는데 이미 visited 되어 있었고, 그런데 그 비용이 더 작으면 어떻게 돼?"

결론부터 말하면,
이런 상황은 '다익스트라 알고리즘이 올바르게 구현되었다면' 절대 발생하지 않는다.

왜 그런가?

다익스트라는 우선순위 큐(min-heap)를 이용해서 항상 가장 비용이 작은 경로부터 꺼내게 돼 있어. 이 말은 즉:

어떤 노드가 처음 큐에서 나오면 그게 그 노드로 가는 가장 짧은 경로라는 것이 보장돼.
이후에 그 노드로 가는 더 긴 경로가 큐에 있을 수는 있지만, 짧은 경로보다 뒤늦게 꺼내지기 때문에 무시해도 된다는 뜻이야.

🔍 왜 가장 짧은 경로가 먼저 나오는가?

우선순위 큐는 내부적으로 힙 자료구조를 사용하기 때문에 항상 가장 작은 값을 먼저 꺼낼 수 있어. 다익스트라에서는 "(현재까지 누적된 비용, 노드)" 형태로 저장되므로, 비용이 작은 경로가 먼저 나오고, 그 경로가 해당 노드의 최소 비용 도달 경로로 확정돼.

예를 들어서 생각해보자

노드 A → B로 가는 경로가 두 개 있다고 하자.

A → B (비용 2)
A → C → B (비용 5)

이 두 경로가 우선순위 큐에 들어갔을 때 순서:

(2, B)
(5, B)

먼저 (2, B)가 꺼내지고 이때 B는 처음 방문되었으므로 seen에 추가돼.
그 다음 (5, B)가 큐에서 나오면? 이미 B in seen 이니까 continue 하고 무시돼.

그런데 네 질문을 다시 강조하자면:

이미 방문했는데 더 짧은 경로로 또 왔다면 어떡하지?

이런 상황이 생겼다는 건, 다익스트라의 전제조건(가장 짧은 경로가 먼저 큐에서 나온다)가 깨졌다는 뜻이야.
즉, 우선순위 큐 정렬이 잘못되었거나, 또는 visited(seen)를 큐에 넣을 때 처리한 오류일 수 있어.

정리하면

상황	처리 방식	이유
큐에서 꺼낼 때 더 짧은 경로로 도달했다	발생할 수 없음	다익스트라는 항상 최단 경로부터 꺼내므로
이런 상황이 생긴다면	구현 오류 가능성	큐에서 꺼내기 전에 visited 처리했을 수도 있음

💡 참고: 다익스트라 알고리즘이 잘 작동하지 않는 경우

다익스트라는 모든 간선 가중치가 0 또는 양수일 때만 올바르게 작동해.
음수 간선이 존재하면 더 짧은 경로가 나중에 발견될 수 있어서, 다익스트라의 "확정된 최단 거리"라는 성질이 무너져.
이럴 땐 벨만-포드 알고리즘처럼 음수 간선을 처리할 수 있는 알고리즘을 써야 해.

핵심 요약

항상 현재까지 가장 빠르게 도달할 수 있는 도시를 기준으로, 더 빠른 길이 있다면 갱신하고, 아니면 무시한다.

낚시하는 곰

취업 준비생 낚곰입니다!! 반갑습니다!!

이전 포스트

위상 정렬

다음 포스트

다익스트라 알고리즘

krafton jungle

다익스트라 알고리즘의 거리 갱신 로직 쉽게 풀기

먼저 비유부터 들어보자

단계별 설명

1단계. 처음엔 모든 도시는 얼마나 걸릴지 몰라

2단계. A에서 갈 수 있는 도시들을 확인해봐

3단계. 이제 메모지를 다시 보고, 가장 시간이 적은 도시(B)를 방문

4단계. 계속 이걸 반복해

함수명

주요 변수명

구현

`seen` vs `visited`의 차이점

1. `seen`

2. `visited`

🌟 예시로 비교해보자

BFS에서의 `visited`

다익스트라에서의 `seen`

🤔 왜 다익스트라는 큐에 넣을 때가 아니라 꺼낼 때 체크할까?

⚠ 예외: A* 알고리즘이나 Dijkstra 변형에서 `visited`를 큐에 넣을 때 처리하는 경우

정리

`set()`이 방문 여부를 체크하는 원리

1. `set`은 중복을 허용하지 않는 자료구조야.

다익스트라에서의 흐름으로 설명해볼게

흐름 요약:

왜 리스트나 딕셔너리가 아니라 `set`을 쓰는 걸까?

왜 힙큐를 사용할까?

왜 그런가?

🔍 왜 가장 짧은 경로가 먼저 나오는가?

예를 들어서 생각해보자

그런데 네 질문을 다시 강조하자면:

정리하면

💡 참고: 다익스트라 알고리즘이 잘 작동하지 않는 경우

핵심 요약

항상 현재까지 가장 빠르게 도달할 수 있는 도시를 기준으로, 더 빠른 길이 있다면 갱신하고, 아니면 무시한다.

위상 정렬

플로이드 워셜 알고리즘

0개의 댓글

다익스트라 알고리즘

krafton jungle

다익스트라 알고리즘의 거리 갱신 로직 쉽게 풀기

먼저 비유부터 들어보자

단계별 설명

1단계. 처음엔 모든 도시는 얼마나 걸릴지 몰라

2단계. A에서 갈 수 있는 도시들을 확인해봐

3단계. 이제 메모지를 다시 보고, 가장 시간이 적은 도시(B)를 방문

4단계. 계속 이걸 반복해

함수명

주요 변수명

구현

seen vs visited의 차이점

1. seen

2. visited

🌟 예시로 비교해보자

BFS에서의 visited

다익스트라에서의 seen

🤔 왜 다익스트라는 큐에 넣을 때가 아니라 꺼낼 때 체크할까?

⚠ 예외: A* 알고리즘이나 Dijkstra 변형에서 visited를 큐에 넣을 때 처리하는 경우

정리

set()이 방문 여부를 체크하는 원리

1. set은 중복을 허용하지 않는 자료구조야.

다익스트라에서의 흐름으로 설명해볼게

흐름 요약:

왜 리스트나 딕셔너리가 아니라 set을 쓰는 걸까?

왜 힙큐를 사용할까?

왜 그런가?

🔍 왜 가장 짧은 경로가 먼저 나오는가?

예를 들어서 생각해보자

그런데 네 질문을 다시 강조하자면:

정리하면

💡 참고: 다익스트라 알고리즘이 잘 작동하지 않는 경우

핵심 요약

항상 현재까지 가장 빠르게 도달할 수 있는 도시를 기준으로, 더 빠른 길이 있다면 갱신하고, 아니면 무시한다.

위상 정렬

플로이드 워셜 알고리즘

0개의 댓글

`seen` vs `visited`의 차이점

1. `seen`

2. `visited`

BFS에서의 `visited`

다익스트라에서의 `seen`

⚠ 예외: A* 알고리즘이나 Dijkstra 변형에서 `visited`를 큐에 넣을 때 처리하는 경우

`set()`이 방문 여부를 체크하는 원리

1. `set`은 중복을 허용하지 않는 자료구조야.

왜 리스트나 딕셔너리가 아니라 `set`을 쓰는 걸까?