[코테 알고리즘] BFS vs 다익스트라

1️⃣ 다익스트라 vs BFS 차이점

알고리즘	WHEN	특징	탐색 방식
BFS	모든 간선의 가중치가 동일할 때(=1)	최단 거리 탐색	큐(FIFO) 사용
다익스트라	간선마다 가중치가 다를 때	가중치 최단 거리 탐색	우선순위 큐(힙) 사용

💡 BFS와 다익스트라 비교

👉 BFS는 모든 간선의 비용이 같을 때 (1 또는 0) 최단 경로를 찾기 좋음.
👉 다익스트라는 각 간선에 가중치(비용)가 다를 때 최단 경로를 찾음.

 

📌 2️⃣ BFS와 다익스트라의 동작 차이

✅ (1) BFS 예제

from collections import deque

def bfs(start):
    queue = deque([start])
    distance[start] = 0  # 시작점의 거리는 0

    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if distance[next_node] == -1:  # 방문하지 않았다면
                distance[next_node] = distance[now] + 1  # 거리 갱신
                queue.append(next_node)

• 모든 간선이 가중치 1일 때 사용 가능
• queue.append()를 사용해서 FIFO 방식으로 탐색
• 한 번 방문한 노드는 최단 경로가 확정됨

✅ (2) 다익스트라 예제 (가중치가 다름)

import heapq  # 우선순위 큐 사용

def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))  # (거리, 노드) 형태로 저장
    distance[start] = 0

    while heap:
        dist, now = heapq.heappop(heap)  # 현재 최단 거리 노드 꺼냄

        if distance[now] < dist:
            continue  # 이미 처리된 경우 건너뛰기

        for next_node, weight in graph[now]:
            cost = dist + weight  # 현재 거리 + 이동 비용
            if cost < distance[next_node]:  # 더 짧은 경로 발견
                distance[next_node] = cost
                heapq.heappush(heap, (cost, next_node))  # 새로운 경로 저장

• 각 간선의 가중치가 다를 때 사용
• heapq(우선순위 큐)를 사용해 가장 작은 거리부터 탐색
• BFS처럼 단순하게 탐색하면 안 되고, 더 짧은 경로를 발견하면 갱신해야 함

heapq.heappop()

• 다익스트라는 현재 가장 짧은 거리의 노드를 먼저 탐색해야 함.
• heapq는 최소 힙(min-heap) 구조를 사용해서 가장 작은 거리(dist)를 가진 노드를 먼저 꺼낼 수 있음.
• BFS처럼 단순한 queue를 쓰면 탐색 순서가 랜덤해질 수 있음 → 잘못된 경로를 먼저 탐색할 위험이 있음.

📌 즉, heapq.heappop()을 쓰는 이유:
✔ 현재까지의 최단 거리가 가장 짧은 노드를 먼저 탐색하기 위

📌 3️⃣ BFS와 다익스트라 실행 과정 비교

✅ BFS 예제 (모든 가중치가 1)

입력:  A → B → C → D
가중치: 1 1 1

1. A(0) → B(1) → C(2) → D(3)  (모든 거리 동일)

 

✔ BFS는 간선 가중치가 동일할 때 최단 거리 선택

✅ 다익스트라 예제 (가중치가 다름)

입력:  A → B → C → D
가중치: 1 5 2

1. A(0) → B(1) (최소 거리 선택)
2. A(0) → B(1) → C(6) ❌  (C로 가는 더 좋은 경로 찾음)
3. A(0) → B(1) → D(3) ✅  (더 짧은 경로로 갱신)

 

✔ BFS로 단순 탐색하면 A → C → D처럼 엉뚱한 경로 선택 가능
✔ 다익스트라는 더 짧은 경로를 계속 갱신하면서 최적의 경로를 선택

🔹 결론

BFS: 모든 간선의 가중치가 1일 때 사용

다익스트라: 가중치가 다를 때 사용 → 우선순위 큐(힙)으로 최소 거리부터 탐색
차이점:

• BFS는 단순 큐 사용 (FIFO)
• 다익스트라는 최소 비용을 우선 탐색해야 하므로 우선순위 큐(힙) 사용