📌 깊이우선탐색(DFS)과 너비우선탐색(BFS)
▶ 해당 개념을 알기 위해서는 세 가지의 개념이 선행되어야 한다.
1) 먼저 자료구조 스택/큐 이해가 필요하다.
스택/큐에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/자료구조-스택Stack큐Queue덱Deque
2) 재귀함수의 호출과 리턴 과정에 대한 이해가 필요하다.
재귀함수에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/Python-재귀함수Recursive-Function
3) 간선과 노드 및 인접행렬과 인접리스트에 대한 그래프 이해가 필요하다.
그래프에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/그래프Graph-인접행렬과-인접리스트
4) BFS/DFS를 처음 접하는 사람은 아래 링크의 유튜브 설명을 보는 것을 추천한다.
BFS/DFS를 이해하기 정말 좋은 영상이고, 이 포스팅도 해당영상을 기반으로 했다.
👉🏻 https://www.youtube.com/watch?v=_hxFgg7TLZQ
▶ 위의 그림은 DFS와 BFS 경로를 순서대로 나타낸 것이다.
해당 그림을 통해 직관적으로 DFS와 BFS의 차이를 알 수 있을 것이다.
깊이우선탐색인 DFS는 가장 깊은 곳까지 방문하고, 너비우선탐색인 BFS는 같은 레벨 인접 노드를 전부 방문한뒤 다음 레벨 인접 노드를 방문한다. DFS는 Stack을 통해 구현하고, BFS는 Queue를 통해 구현한다.
✏️ 깊이우선탐색(DFS) 구현
👉🏻 깊이우선탐색 DFS(Depth-First Search)는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
▶ 깊이우선탐색(DFS) 구현 방법
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
▶ 해당 그래프를 DFS로 구현해보자. DFS는 Stack을 이용한다. Stack은 한 방향에서만 자료를 넣고 뺄 수 있는 후입선출 방식 구조이므로, 가장 늦게 들어온 노드를 가장 먼저 뺄 수 있다. 또한, 한 번 담았던 노드는 다시 담지 않는다.
▶ 먼저 시작 노드인 0번 노드를 스택에 담았다.
▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 스택에 담았다.
▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 스택에 담았다.
▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드와 5번 노드를 스택에 담았다.
2번 노드는 이미 스택에 담겨있으므로 스택에 다시 추가하지 않는다.
▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 스택에 담았다.
▶ 이 후 7번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.
▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 스택에 담았다.
▶ 이 후 8번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.
▶ 이 후 4번 노드를 꺼내 출력하고, 2번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.
DFS 경로 : 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2
💡 출력 순서와 과정은 스택이기 때문에 위와 같이 이루어지는 것이다. 스택은 마치 박스 쌓기와 같아서 가장 늦게 올린 박스를 가장 먼저 꺼낼 수 있다. DFS 구현 과정 또한 스택으로 구현하는 것이기에 가장 위에 있는 노드를 계속 꺼내는 것이다.
✏️ 너비우선탐색(BFS)
👉🏻 BFS(Breadth First Search)는 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.
▶ 너비우선탐색(BFS) 구현 방법
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
▶ 해당 그래프를 BFS로 구현해보자. BFS는 Queue를 이용한다. Queue는 가장 먼저 들어온 것이 가장 먼저 나가는 선입선출 방식의 구조이다. DFS 구현과 마찬가지로 한번 큐에 담았던 노드는 다시 담지 않는다.
▶ 먼저 시작 노드인 0번 노드를 큐에 담았다.
▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 큐에 담았다.
큐는 선입선출이므로 꺼내는 방향이 그림의 화살표처럼 아래부터이다.
▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 큐에 담았다.
▶ 이 후 2번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드를 큐에 담았다.
💡 큐는 선입선출 방식이므로 가장 아래 있는 2번 노드부터 꺼낸다. 또한, 그 인접 노드 중 1번, 3번은 이미 큐에 들어갔었으므로 4번 노드만 큐에 담긴다.
▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 5번 노드를 큐에 담았다.
▶ 이 후 4번 노드를 꺼내 출력하고, 그 인접 노드는 전부 큐에 담았던 적이 있으므로 다시 담지 않는다.
▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 큐에 담았다.
▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 큐에 담았다.
▶ 이 후 7번 노드를 꺼내 출력하고, 8번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.
BFS 경로 : 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8
✏️ DFS와 BFS 예제
백준에서 대표문제인 1260번 DFS와 BFS예제가 있다.
아래 링크에 해당 문제와 구현을 자세히 적어놨다.
https://velog.io/@falling_star3/백준Python-1260번-DFS와BFS
▶ 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)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
dfs(graph, 1, visited)
# 출력
1 2 7 6 8 3 4 5
위와 같이 과정이 이루어진다.
▶ BFS 예제
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
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
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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 
위와 같이 과정이 이루어진다.
참고
<이것이 코딩테스트다>
https://www.youtube.com/watch?v=_hxFgg7TLZQ
