DFS
1. 그래프 구성 예시
다음과 같이 노드 1부터 4까지 연결된 그래프가 있다고 가정해 보겠습니다.
- 노드 1: 2, 3과 연결
- 노드 2: 4와 연결
- 노드 3: 연결 없음
- 노드 4: 연결 없음
이것을 파이썬 리스트(인접 리스트) 형식으로 표현하면 다음과 같습니다.
Python
# 각 인덱스가 노드 번호를 의미 (0번 인덱스는 비워둠)
graph = [
[], # 0번 (사용 안 함)
[2, 3], # 1번 노드와 연결된 노드들
[4], # 2번 노드와 연결된 노드들
[], # 3번 노드와 연결된 노드들
[] # 4번 노드와 연결된 노드들
]
# 방문 여부를 체크할 리스트 (False로 초기화)
visited = [False] * 52. 전체 실행 코드
이제 작성하신 함수를 호출하여 실행해 보겠습니다.
Python
def dfs(graph, v, visited):
# 1. 현재 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 2. 인접한 노드 확인
for i in graph[v]:
# 3. 방문하지 않았다면 재귀 호출
if not visited[i]:
dfs(graph, i, visited)
# 실행 결과 출력
print("DFS 방문 순서:")
dfs(graph, 1, visited)실행 결과: 1 2 4 3
3. 코드 동작 흐름 (Trace)
컴퓨터 내부에서 어떤 순서로 일이 벌어지는지 따라가 볼까요?
- dfs(1) 호출: 1번 방문 처리하고 출력 → 인접 노드인 2번으로 들어감.
- dfs(2) 호출: 2번 방문 처리하고 출력 → 인접 노드인 4번으로 들어감.
- dfs(4) 호출: 4번 방문 처리하고 출력 → 더 이상 갈 곳이 없으므로 dfs(2)로 되돌아감(Return).
- dfs(2) 복귀: 2번에서 더 갈 곳이 없으므로 dfs(1)로 되돌아감.
- dfs(1) 복귀: 1번의 다음 인접 노드인 3번 확인 → 방문 안 했으니 들어감.
- dfs(3) 호출: 3번 방문 처리하고 출력 → 더 갈 곳 없으므로 복귀.
- 종료: 모든 호출이 끝나고 프로그램이 마무리됩니다.
💡 팁: 인접 노드가 여러 개일 때
위 코드에서 노드 1의 인접 노드가 [2, 3]일 때 작은 번호부터 방문하는 이유는 리스트의 앞 순서부터 for 문이 돌기 때문입니다. 만약 방문 순서를 바꾸고 싶다면 graph[v].sort(reverse=True) 등을 사용해 조절할 수 있습니다.
이 예시를 바탕으로 노드 개수를 늘려서 직접 테스트해보시겠어요? 원하신다면 더 복잡한 미로 찾기 같은 응용 예시도 만들어 드릴 수 있습니다.
BFS
BFS(Breadth-First Search, 너비 우선 탐색)는 DFS와 달리 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 재귀를 사용하는 DFS와 달리, BFS는 큐(Queue) 자료구조를 사용하여 구현하는 것이 정석입니다.
1. BFS 코드 구현 (Python)
파이썬에서 큐를 구현할 때는 성능을 위해 collections 모듈의 deque를 주로 사용합니다.
Python
from collections import deque
def bfs(graph, start, visited):
# 1. 시작 노드를 큐에 넣고 방문 처리
queue = deque([start])
visited[start] = True
# 2. 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 3. 해당 노드와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
2. 예시 그래프와 실행
DFS 예시에서 사용했던 것과 동일한 그래프 구조를 사용해 보겠습니다.
Python
# 그래프 준비 (인접 리스트)
graph = [
[],
[2, 3], # 1번 노드는 2, 3과 연결
[4], # 2번 노드는 4와 연결
[], # 3번 노드
[] # 4번 노드
]
# 방문 처리 리스트 초기화
visited = [False] * 5
# BFS 실행
print("BFS 방문 순서:")
bfs(graph, 1, visited)
실행 결과:
1 2 3 4
3. DFS vs BFS 차이점 한눈에 보기
| 구분 | DFS (깊이 우선 탐색) | BFS (너비 우선 탐색) |
| 핵심 도구 | 재귀 또는 스택(Stack) | 큐(Queue) |
| 탐색 방식 | 한 길을 끝까지 파고듦 | 인접한 이웃부터 모두 확인 |
| 주요 특징 | 모든 노드를 방문하고자 할 때 | 최단 경로를 찾을 때 유리 |
| 방문 순서 | 1 -> 2 -> 4 -> 3 | 1 -> 2 -> 3 -> 4 |
💡 동작 원리 요약
BFS는 **"먼저 들어온 노드의 이웃을 먼저 방문"**하는 방식입니다.
- 1번을 큐에 넣습니다. [1]
- 1번을 꺼내고, 1의 이웃인 2와 3을 큐에 넣습니다. [2, 3]
- 2번을 꺼내고, 2의 이웃인 4를 큐에 넣습니다. [3, 4]
- 3번을 꺼냅니다. (이웃 없음) [4]
- 4번을 꺼냅니다. (이웃 없음) [] (종료)