[코딩 공부] DFS/BFS (2) - DFS/BFS 알고리즘

프로그래밍/코딩 공부 시리즈 : DFS/BFS

이번 포스팅에서는 지난 포스팅에 이어서 DFS/BFS 알고리즘을 본격적으로 다뤄보겠습니다.

그래프(Graph) 표현 방식

DFS를 이해하기 전에 그래프에 대해 먼저 짚고 넘어가겠습니다. 그래프는 노드(Node) 와 간선(Edge) 으로 구성됩니다. 노드는 정점이라고도 하며, 그래프 탐색은 특정 노드를 시작으로 다수의 노드를 방문하는 것을 의미합니다. 간선으로 연결된 두 노드는 인접(adjacent) 하다고 표현합니다.

그래프를 코드로 표현하는 방식은 두 가지입니다.

인접 행렬(Adjacency Matrix)

INF = 9999999999999999  # 연결되어 있지 않음을 의미

graph = [
    [0, 7, 5],    # 0은 자기 자신, INF는 미연결, 나머지는 이동 비용
    [7, 0, INF],
    [5, INF, 0]
]

인접 리스트(Adjacency List)

# 3개의 노드 정의
graph = [[] for _ in range(3)]

# 0번 노드의 연결 정보
graph[0].append((1, 7))
graph[0].append((2, 5))

# 1번 노드의 연결 정보
graph[1].append((0, 7))

# 2번 노드의 연결 정보
graph[2].append((0, 5))

두 방식 비교

| 구분 | 인접 행렬 | 인접 리스트 | |---|---|---| | 메모리 | 비효율적 (미연결 정보도 저장) | 효율적 (연결된 정보만 저장) | | 두 노드 연결 여부 확인 속도 | 빠름 O(1) | 느림 O(V) | | 적합한 경우 | 노드 수가 적고 간선이 많을 때 | 노드 수가 많고 간선이 적을 때 |

1. DFS (Depth-First Search) — 깊이 우선 탐색

DFS는 그래프에서 가장 깊은 곳을 우선으로 탐색하는 알고리즘입니다. 스택 자료구조를 이용하며, 재귀 함수로 간결하게 구현할 수 있습니다.

동작 방식

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 수행할 수 없을 때까지 반복한다.

구현 예제

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * 9

def dfs(g, node, visit):
    visit[node] = True
    print(str(node) + ' ')
    for v in g[node]:
        if not visit[v]:
            dfs(g, v, visit)

dfs(graph, 1, visited)

2. BFS (Breadth-First Search) — 너비 우선 탐색

BFS는 DFS와 달리 인접한 노드를 우선으로 탐색하는 알고리즘입니다. 선입선출(FIFO) 큐 자료구조를 활용합니다.

일반적으로 DFS보다 수행 시간이 좋은 편입니다.

동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번 과정을 반복할 수 없을 때까지 반복한다.

구현 예제

from collections import deque

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * 9

def bfs(g, node, visit):
    queue = deque([node])
    visit[node] = True
    while queue:
        v = queue.popleft()
        print(v)
        for i in g[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True

bfs(graph, 1, visited)

DFS vs BFS 정리

| 구분 | DFS | BFS | |---|---|---| | 탐색 방식 | 깊이 우선 | 너비 우선 | | 자료구조 | 스택(재귀) | 큐(deque) | | 수행 시간 | 상대적으로 느림 | 상대적으로 빠름 | | 적합한 문제 | 경로 탐색, 사이클 감지 | 최단 경로, 레벨 탐색 |