[암기 필요!] 코딩 테스트 필수 알고리즘 총정리: BFS, DFS, MST, 최단 경로 알고리즘

들어가며

코딩 테스트를 준비하는 개발자라면 누구나 한 번쯤 마주치는 그래프 탐색과 최단 경로 문제. 이 글에서는 코딩 테스트에서 자주 출제되는 핵심 알고리즘들을 Python 코드와 함께 정리했습니다.

💡 Tip: 이 알고리즘들은 시험장에서 바로 떠올리기 어려울 수 있으므로, 반드시 외워두시기 바랍니다.

---

1. 그래프 탐색 알고리즘

1.1 BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 가까운 노드부터 탐색하는 알고리즘으로, 큐(Queue) 자료구조를 사용합니다. 미로 찾기, 최단 거리 탐색 등에 자주 등장합니다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

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

시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수)

1.2 DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 한 방향으로 끝까지 파고드는 방식으로 동작하며, 재귀함수 또는 스택을 사용할 수 있습니다.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

시간 복잡도: O(V + E)

---

2. 최소 신장 트리 (MST) 알고리즘

2.1 크루스칼 알고리즘 (Kruskal's Algorithm)

간선 중심으로 최소 신장 트리를 구하는 알고리즘입니다. 유니온-파인드(Union-Find) 자료구조를 사용합니다.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    root_a = find(parent, a)
    root_b = find(parent, b)
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # (a, b, cost)
    parent = [i for i in range(n)]
    mst_weight = 0

    for a, b, cost in edges:
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            mst_weight += cost
    return mst_weight

시간 복잡도: O(E log E)

2.2 프림 알고리즘 (Prim's Algorithm)

노드 중심으로 최소 신장 트리를 구성하며, 우선순위 큐(Heap)를 사용합니다.

import heapq

def prim(graph, start):
    visited = set()
    min_heap = [(0, start)]
    total_cost = 0

    while min_heap:
        cost, node = heapq.heappop(min_heap)
        if node not in visited:
            visited.add(node)
            total_cost += cost
            for neighbor, weight in graph[node]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (weight, neighbor))
    return total_cost

시간 복잡도: O(E log V)

---

3. 최단 경로 알고리즘

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

한 정점에서 다른 모든 정점까지의 최단 거리를 구합니다. 우선순위 큐(Heap)를 사용합니다.

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    hq = [(0, start)]

    while hq:
        cost, node = heapq.heappop(hq)
        if cost > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(hq, (new_cost, neighbor))
    return dist

시간 복잡도: O(E log V)

3.2 플로이드-워셜 알고리즘 (Floyd-Warshall)

모든 정점 간의 최단 거리를 구하는 알고리즘으로, 동적 계획법(DP)을 활용합니다.

def floyd_warshall(n, graph):
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    for u, v, w in graph:  # (u -> v 가중치 w)
        dist[u][v] = min(dist[u][v], w)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

시간 복잡도: O(V³)

---

알고리즘 선택 가이드

상황	추천 알고리즘
최단 경로 (단일 출발점)	다익스트라
최단 경로 (모든 쌍)	플로이드-워셜
최소 신장 트리 (간선이 적은 경우)	크루스칼
최소 신장 트리 (간선이 많은 경우)	프림
그래프 탐색 (최단 경로 필요)	BFS
그래프 탐색 (모든 경로 필요)	DFS

---

마무리

이 알고리즘들은 대부분의 그래프 문제에서 핵심으로 작동하며, 코딩 테스트뿐 아니라 실무에서도 자주 사용됩니다. 특히 다음과 같은 상황에서 유용합니다:

1. BFS: 최단 경로 탐색, 레벨 순서 탐색
2. DFS: 사이클 탐지, 위상 정렬
3. MST: 네트워크 설계, 클러스터링
4. 최단 경로: 네비게이션, 라우팅

⚠️ 주의사항: 알고리즘을 이해하는 것도 중요하지만, 실제로 구현해보고 문제에 적용해보는 연습이 더욱 중요합니다.

---

참고 자료

• Python 공식 문서
• GeeksforGeeks - Graph Algorithms
• LeetCode - Graph Problems