우리가 알고리즘을 공부하면서 마주치는 수많은 문제들 — 예를 들면 미로 탈출, 경로 찾기, 친구 관계 분석, 조직도 순회 등 —은 겉보기에는 다양해 보이지만 결국 "대상들 간의 연결 관계를 어떻게 탐색할 것인가"라는 문제로 귀결된다.
이때 필요한 개념이 바로 그래프(Graph)다. 그래프는 노드(정점)과 간선(연결선)으로 이루어져 있으며, 정점은 어떤 대상(예: 도시, 사람, 웹페이지 등)을, 간선은 그들 사이의 관계(예: 도로, 친구 관계, 하이퍼링크 등)를 나타낸다.
그래프를 활용한 문제를 해결하려면, 그래프 자체를 어떤 방식으로 표현할 것인가가 먼저 결정되어야 한다.
이를 위해 보통 그래프를 코드로 표현하는 두 가지 방식, 즉 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 사용된다.
인접 행렬
인접 행렬은 그래프의 연결 관계를 2차원 배열로 표현하는 방식이다. 노드의 개수가 V개일 때, V x V 크기의 배열을 생성하여 arr[a][b] = 1이면 a에서 b로 가는 간선이 존재함을 의미하고, 연결이 없다면 0으로 표현한다. 이 방식은 구현이 간단하고 두 노드가 연결되어 있는지 확인할 때 매우 직관적이다. 예를 들어 arr[2][5] == 1이라면 2번 노드와 5번 노드가 연결되어 있다는 뜻.
하지만 이 방식은 모든 노드 간의 관계를 저장하기 때문에, 실제로 간선이 많지 않은 희소 그래프에서는 불필요한 공간 낭비가 발생할 수 있다.
- 장점: 연결 여부를 O(1)로 확인할 수 있음
- 단점: 공간 복잡도 O(V²), 연결된 노드 탐색 시 O(V) 시간 필요
인접 리스트
인접 리스트는 각 노드가 연결된 노드들을 리스트로 저장하는 방식이다. 예를 들어 arr[3] = [2, 4, 7]이라면, 3번 노드는 2번, 4번, 7번 노드와 연결되어 있다는 의미다. 이 방식은 간선이 많지 않은 그래프에서 훨씬 효율적이며, 필요한 연결만 저장하므로 공간 낭비가 거의 없다. 그래서 대부분의 그래프 문제에서는 인접 리스트 방식으로 구현하는 것이 일반적이다.
- 장점: 공간 효율성 높음 (O(V + E)), 연결된 노드 순회가 빠름
- 단점: 리스트를 순회해야 하므로 최악의 경우 O(V), 평균적으로는 O(연결된 노드 수)
그런데 어떤 문제들은 그래프 중에서도 좀 더 단순한 구조를 갖고 있는 경우가 있다.
예를 들어 조직도, 파일 디렉터리, 이진 탐색 트리 같은 구조는 사이클이 없고, 방향이 있으며, 루트에서 시작해서 내려가는 구조를 갖고 있다. 이런 구조를 우리는 트리(Tree)라고 부른다. 트리는 루트에서 시작해 자식 노드로만 향하는, 사이클이 없는 방향 그래프(DAG)의 일종이다.
이런 트리 구조 또한 결국은 그래프의 한 종류이기 때문에, 트리를 포함한 다양한 그래프 구조에서 어떻게 노드를 순서대로 방문할 것인지가 중요한 문제가 된다.
그래프 탐색이란?
그래프 탐색은 말 그대로 그래프에 존재하는 모든 정점을 한 번씩 방문하는 과정을 의미한다.
이때 사용할 수 있는 대표적인 알고리즘이 바로:
- DFS (Depth-First Search): 깊이 우선 탐색
- BFS (Breadth-First Search): 너비 우선 탐색
이 두 탐색 방식은 구조적으로는 간단하지만, 탐색 순서와 용도에 따라 성능이나 효율성에서 큰 차이를 보일 수 있으므로 정확한 이해가 필요하다. 그리고 이 차이는 단지 동작 방식에만 국한되지 않는다. DFS와 BFS는 실제로 구현하는 방식에서도 뚜렷한 차이를 보인다.
DFS는 가능한 한 깊이 들어가며 탐색을 진행하고, 더 이상 갈 곳이 없을 때 되돌아오는 방식이다.
이런 특성 때문에 DFS는 다양한 방식으로 구현할 수 있다. 함수 호출 스택을 이용한 재귀 방식, 직접 스택을 사용하는 명시적 구현(list), 그리고 deque를 스택처럼 활용하는 방식 등이 모두 가능하다. 한 경로를 끝까지 따라가는 탐색 흐름이 스택 구조와 자연스럽게 맞물리기 때문이다.
반면 BFS는 가까운 정점부터 탐색을 넓혀가는 방식이다. 같은 레벨에 있는 정점들을 먼저 탐색하고, 그 다음 레벨로 넘어간다. 이런 탐색 구조는 큐를 사용해야만 자연스럽게 구현할 수 있다. 스택이나 재귀는 깊이 우선 흐름이기 때문에, BFS처럼 레벨을 기준으로 탐색하는 구조에는 적합하지 않다.
결과적으로 DFS는 여러 방식으로 구현할 수 있지만, BFS는 큐를 사용하는 방식이 유일하게 실용적이다.
파이썬에서는 이 큐를 구현할 때 collections 모듈의 deque를 사용하는 것이 일반적이다.
이처럼 DFS와 BFS는 구현 방식에도 차이가 있지만, 실제 문제 상황에서 어떤 탐색이 더 적절한지를 판단하는 것이 더욱 중요하다.
DFS는 한 경로를 끝까지 탐색하고 돌아오는 구조를 가지고 있기 때문에, 다음과 같은 문제에 자주 활용된다:
- 최소값이나 최대값을 구해야 하는 경우
- 가능한 모든 경우의 수를 탐색해야 하는 경우
- 조건을 만족하지 않으면 되돌아가 다른 경로를 탐색해야 하는 백트래킹 문제
(예: N-Queen, 특정 경로 조건 만족 여부 판단 등)
반면, BFS는 거리나 탐색 단계(레벨)를 기준으로 탐색을 진행하기 때문에 다음과 같은 상황에 적합하다:
- 특정 지점에 도달하기까지의 최단 거리를 구해야 하는 문제
- 격자형(2차원 배열) 구조에서 상하좌우로 한 칸씩 움직이며 퍼지는 유형의 문제
(예: 미로 탈출, 불의 확산, 바이러스 전파 등)
DFS (깊이 우선 탐색)
DFS는 가능한 한 깊게 그래프의 정점을 탐색한 후, 더 이상 갈 곳이 없으면 다시 돌아가 다른 경로를 탐색하는 방식이다. 트리 구조에서는 루트에서 리프까지 한 경로를 끝까지 따라가며 탐색하는 전위 순회(Preorder Traversal)와 같은 방식이기도 하다.
구현 방식
DFS는 크게 세 가지 방식으로 구현할 수 있다:
1. 재귀 방식 (Recursive DFS)
함수 호출 스택을 이용해 구현하며 코드가 가장 간결하다.
하지만 탐색 깊이가 깊을 경우, 재귀 깊이 초과(RecursionError) 가 발생할 수 있다.
이 경우 sys.setrecursionlimit()으로 제한을 늘리거나, 스택 방식으로 대체하는 것이 좋다.
- 시간 복잡도: O(V + E) : 모든 정점(V)과 간선(E)을 한 번씩 방문하기 때문
- 공간 복잡도: O(V) : 방문 배열 외에 재귀 호출 스택이 최대 O(V) 깊이까지 쌓일 수 있음
- 기본 탐색 순서: 인접 노드를 순서대로 방문하므로, 그래프를 사전순으로 정렬해두었다면 보통 사전식(오름차순) 순서로 탐색되는 경우가 많다
def dfs_recursive(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs_recursive(graph, i, visited)
2. 명시적 스택 방식 (list 사용)
재귀 대신 list를 명시적인 스택으로 사용하여 DFS를 구현할 수 있다.
후입선출(LIFO)을 위해 reversed()를 활용하며, 탐색 순서를 맞춰준다.
- 시간 복잡도: O(V + E) : 역시 모든 노드와 간선을 한 번씩 확인
- 공간 복잡도: O(V) : stack이 최악의 경우 모든 노드를 담을 수 있으며, reversed(graph[v]) 사용 시, 리스트 복사 비용이 약간 발생할 수 있음.
- 기본 탐색 순서: 인접 노드를 그대로 스택에 넣으면, 스택 특성상 역순(내림차순)으로 탐색되는 경향이 있다.
원하는 순서로 방문하려면 reversed() 또는 정렬을 조정해야 한다.
def dfs_stack_list(graph, start):
visited = [False] * len(graph)
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
print(v, end=' ')
for i in reversed(graph[v]):
stack.append(i)
3. 명시적 스택 방식 (deque 사용)
list 대신 collections.deque를 스택처럼 사용하면 pop/append 연산이 더 빠르고 안정적이다.
큐뿐 아니라 스택에도 deque를 활용할 수 있다.
- 시간 복잡도: O(V + E) : 마찬가지로 전체 정점과 간선을 한 번씩 탐색
- 공간 복잡도: O(V) : 스택 최대 깊이만큼 노드가 저장되며 deque는 list보다 안정적으로 pop/append를 O(1)로 처리
- 기본 탐색 순서: 스택 구조이기 때문에 역순(내림차순) 탐색되는 경우가 많다.
from collections import deque
def dfs_stack_deque(graph, start):
visited = [False] * len(graph)
stack = deque([start])
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
print(v, end=' ')
for i in reversed(graph[v]):
stack.append(i)
동작 방식 (재귀적 설명)
- 현재 정점을 방문 처리한다.
- 인접한 정점 중 방문하지 않은 정점이 있으면 그 정점으로 이동해 다시 1번부터 수행한다.
- 모든 인접 정점을 다 방문했으면 이전 정점으로 되돌아간다.
스택 구조 예시:
방문 순서: 1 → 2 → 4 → 5 → ...
스택 상태: [1] → [2] → [4] → [5]
DFS 구현 시 주의할 점
- 재귀 방식에서는 시스템 호출 스택이 사용되므로, 경로 깊이에 따라 스택 오버플로우가 발생할 수 있다.
- 명시적 스택 방식은 이런 문제를 피하면서 탐색 순서를 명확히 제어할 수 있다.
- 탐색 도중 이미 방문한 노드를 다시 방문하지 않도록 visited 배열을 반드시 사용해야 한다.
- 백트래킹(Backtracking)은 DFS의 핵심 기법으로, 특정 조건을 만족하지 못하는 경로에서 되돌아가 다른 경로를 탐색하는 데 사용된다.
- 연결되지 않은 그래프의 경우 모든 정점에 대해 DFS를 한 번씩 수행해야 전체 순회를 보장할 수 있다.
코딩 테스트 팁
- DFS는 "끝까지 파고들기" 전략이기 때문에 모든 경우의 수를 따져야 하는 문제에서 자주 등장한다.
- 특히 "조건에 맞는 경우만 골라라", "경로를 모두 탐색하라"는 유형의 문제에서 자주 등장하며, 백트래킹과도 밀접하게 연결된다.
- DFS 기반 문제에서는 방문 처리를 안 하면 무한 루프에 빠지므로, visited 체크가 필수
- 재귀 깊이가 10만 이상인 경우는 Python에서는 기본적으로 에러가 나므로 sys.setrecursionlimit(10**6) 같은 설정이 필요한 경우도 있다.
BFS (너비 우선 탐색)
BFS는 현재 노드에서 가까운 노드들부터 차례대로 탐색한 후, 그 노드들과 연결된 다음 노드들을 이어서 탐색하는 방식이다. 탐색 순서가 계층적이기 때문에 최단 거리를 구하는 문제에서 매우 자주 쓰인다.
구현 방식
BFS는 큐(Queue) 자료구조를 기반으로 동작하며, Python에서는 다음과 같은 방식으로 구현한다.
1. list 기반 구현
일반 리스트를 큐처럼 사용하며 `pop(0)`으로 앞 요소를 꺼낸다. 다만 `pop(0)` 연산은 O(N)이므로 성능상 비효율적이다.
def bfs_list(graph, start):
visited = [False] * len(graph)
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
2. deque 기반 구현
collections 모듈의 deque를 사용하면 popleft()가 O(1)로 매우 효율적이다. 코딩 테스트에서는 이 방식이 가장 일반적이다.
from collections import deque
def bfs_deque(graph, start):
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
3. 재귀 방식
BFS는 본질적으로 큐 기반 반복 구조에 적합하며, 재귀 방식은 일반적으로 추천되지 않는다. 재귀로 구현하는 경우도 있지만, 엄밀한 BFS의 계층적 구조를 유지하기 어렵고 실전에서는 거의 사용되지 않는다.
def bfs_recursive(graph, queue, visited):
if not queue:
return
v = queue[0]
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
queue.pop(0)
bfs_recursive(graph, queue, visited)
동작 방식
- 시작 정점을 큐에 넣고 방문 처리
- 큐에서 정점을 꺼내고, 인접한 방문하지 않은 정점들을 큐에 추가
- 큐가 빌 때까지 2번을 반복
큐 구조 예시:
방문 순서: 1 → 2 → 3 → 4 → ...
큐 상태: [1] → [2,3] → [3,4] → [4,...]
큐에 넣을 때 바로 visited 체크를 하는 이유는, 동일한 노드가 중복 삽입되는 것을 방지하기 위함이다.
BFS 활용 팁
- 탐색 경로를 넓게 확장하므로, 탐색 레벨을 기준으로 결과를 도출할 수 있다
- 최단 거리 문제에서는 distance[i] = distance[cur] + 1 방식으로 거리 누적
- 무방향/방향 그래프 모두 사용 가능하나, 방향성 주의 필요
- 2차원 배열 탐색(미로, 섬, 불 퍼짐, 바이러스 등)에서 거의 필수로 사용됨
- 여러 시작점이 있는 경우, 시작 노드들을 모두 큐에 넣고 동시에 탐색 시작하는 방식도 자주 사용된다
코딩 테스트 팁
- BFS는 "가장 빨리 도달할 수 있는 곳이 어딘가?" 같은 문제에서 쓰이며, "최단 거리"는 거의 대부분 BFS
- 특히 2차원 배열에서의 탐색(ex. 미로, 섬, 불 퍼짐, 바이러스 등)은 BFS가 기본
- distance = [[-1]*n for _ in range(m)] 형태의 거리 배열을 함께 사용하는 경우가 많다.
- 여러 시작점이 있을 경우, 시작점들을 모두 큐에 넣고 동시에 시작하는 BFS도 자주 사용된다. (예: 여러 바이러스가 동시에 퍼질 때).
참고
'Algorithm > Deep Dive' 카테고리의 다른 글
| [Algorithm] 다익스트라 알고리즘 (Dijkstra algorithm) (0) | 2025.04.27 |
|---|---|
| [Algorithm] 재귀(Recursion) 알고리즘 (1) | 2025.03.30 |
| [Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes)란? (0) | 2025.03.05 |