[TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색
그래프를 탐색하는 방법에는
DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다
그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다
1. DFS
Depth-First Search, 깊이 우선 탐색
최대한 깊이 내려가고, 더 이상 깊이 내려갈 곳이 없을 경우 옆으로 이동
모든 노드를 방문하는 경우에 사용한다
* 스택 또는 재귀를 이용해서 구현
시간 복잡도 - 인접 리스트 O(V+E), 인접 행렬 O(V^2)
DFS 기본 원칙
"앞으로 찾아 가야할 노드" 와 "이미 방문한 노드" 를 기준으로 데이터 탐색한다
경로 찾기, 탐색 문제, 백트래킹, 사이클 탐지 등에 유용하다
DFS 코드 구현
탐색 순서
1 - 2 - 4 - 5 - 3 - 6
4 방문 후 2로 백트래킹하여 5를 방문하고, 다시 2 - 1로 백트래킹하여 3과 6을 방문한다
1. 스택 자료 구조 이용
def dfs(graph, start):
# 방문 여부를 기록하는 리스트
visited = [False] * len(graph)
# 스택 초기화 (시작 노드 넣기)
stack = [start]
while stack:
# 스택에서 노드를 꺼냄
v = stack.pop()
# 방문하지 않았다면 방문 처리
if not visited[v]:
print(v, end=' ') # 방문하지 않았다면 방문 처리
visited[v] = True
# 연결된 노드를 스택에 추가
# stack 은 LIFO 기 때문에 역순으로 넣어야 DFS 순서와 일치
for neighbor in reversed(graph[v]):
if not visited[neighbor]:
stack.append(neighbor)
# 예시 그래프 (인접 리스트로 표현)
graph = [
[], # 0번 노드는 사용하지 않음 (노드 번호를 1부터 시작하기 위해)
[2, 3], # 1번 노드와 연결된 노드들
[4, 5], # 2번 노드와 연결된 노드들
[1, 6], # 3번 노드와 연결된 노드들
[2], # 4번 노드와 연결된 노드들
[2], # 5번 노드와 연결된 노드들
[3], # 6번 노드와 연결된 노드들
]
# DFS 비재귀적 호출
dfs(graph, 1)
# 줄바꿈
print()
# 결과 출력
# 1 2 4 5 3 6스택에 추가할 때 주의할 점
not visited[neighbor] 인 노드를 역순으로 추가해준다
Stack 은 LIFO 구조이기 때문에 역순으로 추가해야 작은 번호인 노드부터 탐색하게 된다
2. 재귀 이용
# 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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
[], # 0번 노드는 사용하지 않음 (노드 번호를 1부터 시작하기 위해)
[2, 3], # 1번 노드와 연결된 노드들
[4, 5], # 2번 노드와 연결된 노드들
[1, 6], # 3번 노드와 연결된 노드들
[2], # 4번 노드와 연결된 노드들
[2], # 5번 노드와 연결된 노드들
[3], # 6번 노드와 연결된 노드들
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (방문 기록)
visited = [False] * 7
# 정의된 DFS 함수 호출, 1번 노드부터 탐색 시작
dfs(graph, 1, visited)
2. BFS
Breadth-First Search, 너비 우선 탐색
최대한 넓게 이동하고, 더 이상 갈 수 없을 때 아래로 이동
시작 정점으로부터 가까운 정점을 먼저 방문하고 떨어져 있는 정점을 나중에 방문하는 순회 방법
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 BFS 사용
* 큐를 이용해서 구현
시간 복잡도 - 인접 리스트 O(V+E), 인접 행렬 O(V^2)
BFS 기본 원칙
"현재 노드의 인접 노드" 를 기준으로 탐색한다
최단 경로 찾기, 레벨 탐색, 최소 이동 거리 계산 등에 유용하다
BFS 코드 구현
탐색 순서
1 - 2 - 3 - 4 - 5 - 6
0 레벨 (1) - 1 레벨 (2, 3) - 2 레벨 (4, 5, 6) 순으로 방문한다
1. 큐 구조 이용 (우선순위 큐 사용)
from collections import deque
def bfs(graph, start):
# 방문 여부를 기록하는 리스트
# 각 노드에 대해 방문했는지 여부를 표시
visited = [False] * len(graph)
# 큐 초기화 (시작 노드 넣기)
# deque 를 생성하기 위해 인자로 리스트를 전달
queue = deque([start])
while queue:
# 큐에서 노드를 꺼냄
v = queue.popleft()
# 방문하지 않았다면 방문 처리
if not visited[v]:
print(v, end=' ') # 방문하지 않았다면 방문 처리
visited[v] = True # 방문한 노드 표시
# 연결된 노드를 큐에 추가
for neighbor in graph[v]:
if not visited[neighbor]: # 아직 방문하지 않은 이웃 노드
queue.append(neighbor) # 이웃 노드를 큐에 추가
if __name__ == '__main__':
# 예시 그래프 (인접 리스트로 표현)
graph = [
[], # 0번 노드는 사용하지 않음 (노드 번호를 1부터 시작하기 위해)
[2, 3], # 1번 노드와 연결된 노드들
[4, 5], # 2번 노드와 연결된 노드들
[1, 6], # 3번 노드와 연결된 노드들
[2], # 4번 노드와 연결된 노드들
[2], # 5번 노드와 연결된 노드들
[3], # 6번 노드와 연결된 노드들
]
# BFS 비재귀적 호출
bfs(graph, 1)
# 줄바꿈
print()
# 결과 출력
# 1 2 3 4 5 6dfs 와 달리, 큐 (스택) 초기화 시 queue = deque([start]) 처럼 괄호를 넣는 이유
deque 는 deque 객체를 생성하는데 사용되며, 초기화할 때 인자로 iterable 한 자료 구조 (리스트, 튜플 등) 을 받는다
괄호 없이 deque 를 사용하면 start 노드 하나만으로 deque 를 만들 수 없기 때문에, 괄호 안에 리스트 형태로 제공해준다