그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 이를 이해하기 위해 먼저 그래프의 기본 개념을 살펴보자.
그래프(Graph)
그래프는 노드(Node, 정점) 와 간선(Edge) 으로 이루어진 자료구조다. 프로그래밍에서 그래프를 표현하는 방식은 크게 두 가지가 있으며, 코딩 테스트에서는 이 두 방식 모두 필요하다.
그래프 표현 방식
인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식
인접 행렬 방식 (Adjacency Matrix)
파이썬에서는 2차원 리스트를 사용하여 인접 행렬을 구현할 수 있다. 연결되지 않은 노드끼리는 무한대(INF)로 표현한다.
INF = 999999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]인접 리스트 방식 (Adjacency List)
각 노드에 연결된 노드를 리스트로 저장한다. 파이썬에서는 리스트의 append() 메서드를 활용하여 구현할 수 있다.
graph = [[] for _ in range(3)]
graph[0].append((1, 7))
graph[0].append((2, 5))
graph[1].append((0, 7))
graph[2].append((0, 5))두 방식의 차이
- 메모리 사용량: 인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심하지만, 인접 리스트는 연결된 정보만 저장하므로 더 효율적이다.
- 탐색 속도: 특정 노드와 연결 여부를 확인하는 경우, 인접 행렬은
graph[a][b]한 번만 조회하면 되지만, 인접 리스트는 노드a의 연결 리스트를 순차적으로 확인해야 한다.
DFS (Depth-First Search, 깊이 우선 탐색)
DFS는 스택(Stack) 자료구조를 이용하여 구현할 수 있다. 또는 재귀 함수를 활용하여 간결하게 표현할 수도 있다.
DFS 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택의 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문할 인접 노드가 없다면 스택에서 최상단 노드를 제거한다.
- 위 과정을 반복하여 더 이상 수행할 수 없을 때까지 진행한다.
DFS 구현 (재귀 함수 사용)
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)1 2 7 6 8 3 4 5
BFS (Breadth-First Search, 너비 우선 탐색)
BFS는 큐(Queue) 자료구조를 사용하며, deque 라이브러리를 활용하면 더욱 효율적으로 구현할 수 있다.
BFS 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.
BFS 구현 (큐 사용)
from collections import deque
def bfs(graph, start, visited):
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
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)1 2 3 8 7 4 5 6
DFS vs BFS 비교
| 알고리즘 | 사용 자료구조 | 탐색 방식 | 시간 복잡도 |
|---|---|---|---|
| DFS | 스택 (재귀 사용 가능) | 깊이 우선 | O(N) |
| BFS | 큐 (deque 활용) | 너비 우선 | O(N) |
- DFS는 깊이 우선 탐색이므로 특정 경로를 깊이 있게 탐색할 때 유리하다.
- BFS는 너비 우선 탐색이므로 최단 경로 탐색에 유리하다.
- 일반적으로 BFS가 DFS보다 수행 시간이 더 빠른 경우가 많다.
결론
DFS와 BFS는 그래프 탐색의 기본이 되는 중요한 알고리즘이다. 각각의 특징과 구현 방식을 숙지하고, 문제 유형에 따라 적절한 알고리즘을 선택하는 것이 중요하다. 추가로, 코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다는 점을 알아두자.
