DFS, BFS
그래프 탐색 알고리즘: DFS, BFS
그래프 탐색, 여기서 말하는 그래프란 정점과 간선으로 이루어진 자료구조의 일종이며 그래프를 탐색하는 것은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다.
이러한 그래프 자료구조를 탐색하는 알고리즘으로 대표적인 DFS(Depth-First Search), BFS(Breadth-First Search)가 있습니다. 두 알고리즘을 공부하기 위해서 자료구조 기초 개념을 이해하는 과정이 선행되어야 합니다.
그럼 스택, 큐 그리고 재귀함수라는 세가지 개념을 먼저 살펴보도록 하겠습니다.
자료구조 기초 개념: 스택, 큐 / 재귀 함수
스택 자료구조
먼저 들어온 데이터가 나갈 때는 나중에 나가는 형식의 자료구조로 상자에 물건을 차곡 차곡 쌓았을 때 마지막에 넣은 것부터 꺼낼 수 있는 개념과 같습니다.
이런 스택 자료구조의 방식을 FILO(First-In-Last-Out)라고 합니다.
큐 자료구조
스택 자료구조와 대조되게 먼저 들어온 데이터가 먼저 나가는 형식(First-In-First-Out)으로 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화할 수 있습니다.
리스트로 구현하는게 불가능한 건 아니지만 시간 복잡도가 더 높아 비효율적으로 동작할 수 있고, 코드 구조가 지저분해지기 쉽기 때문에 deque 라이브러리를 사용합니다.
재귀 함수(Recursive function)
자기 자신을 다시 호출하는 함수를 의미합니다. 이런 재귀 함수는 다시 호출한 함수 내에서 또 다시 재귀 함수를 만나게 되는데, 그렇기 때문에 반드시 재귀 호출을 멈출 조건을 구성해줘야 합니다. 조건이 없다면, 무한하게 재귀를 돌게 되기 때문입니다.
DFS
루트 노드 혹은 다른 임의의 노드에서 시작한 후 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 DFS 라고 부릅니다. 예를 들면 미로 찾기를 할 때 한 방향으로 갈 수 있는 곳까지 쭉 가보고 난 후, 다시 가장 가까운 갈림길로 돌아와서 그 갈림길로 부터 다시 다른 방향으로 탐색을 진행하는 것이 DFS 방식으로 길을 찾는 것입니다. DFS는 이런 특징을 갖습니다.
- 모든 노드를 방문하고자 하는 경우에 적합합니다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단합니다.
- BFS보다 탐색하는 속도가 느립니다.
이런 DFS 알고리즘은 스택과 재귀 함수를 이용해서 구현할 수 있는데, 재귀 함수를 이용하는 것이 가장 보편적이며 또한 간결하게 코딩할 수 있습니다.
BFS
BFS는 루트 노드 혹은 다른 임의의 노드에서 시작한 후 인접한 노드를 먼저 탐색합니다. 앞서 공부한 DFS와는 대조되는 것이죠. 가장 깊은 곳을 우선적으로 탐색하는 DFS와 가장 가까운 곳은 우선적으로 탐색하는 BFS, 둘의 차이점을 확실하게 느낄 수 있습니다. BFS도 동일한 깊이의 노드가 여러 개 있는 상황에서 노드의 번호가 작은 것부터 순서대로 탐색한다는 점을 참고하세요. BFS는 어떤 특징을 가질까요?
- 시작 정점으로부터 가까운 노드부터 방문하고 멀리 떨어져 있는 정점은 나중에 방문하기 때문에 주로 두 노드 사이에 최단 경로를 찾고 싶을 때 사용됩니다.
이런 BFS는 큐로 구현할 수 있습니다.
그래서 DFS, BFS 를 어떻게 쓰면 되나요?
어떤 건지는 알겠는데, 어떻게 쓰면 될지 의문이 드는데요.
그래프의 모든 정점을 방문하는 것이 중요할 때
DFS, BFS 중에 무엇을 사용해도 됩니다.
경로의 특징을 저장해둬야 하는 문제
각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 되는 때나 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
최단거리를 구해야 하는 문제
DFS는 처음으로 발견되는 답이 최단거리가 아닐 수 있지만, BFS는 가까운 곳부터 탐색하기 때문에 처음으로 발견되는 답이 곧 최단거리이기 때문에 BFS를 사용합니다.
백준 문제
[Silver II] DFS와 BFS - 1260
성능 요약
메모리: 39532 KB, 시간: 160 ms
분류
그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)
문제 설명
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
접근 방법
먼저 정점의 개수에 맞게, 정점의 개수가 n 개라면 n * n 그래프를 False 요소로 만들고 방문했는지 체크하기 위해 n 개 요소의 리스트도 False 로 만듭니다.
그리고 해당 노드를 리스트에서 방문하지 않았고 해당 노드에 어떤 노드가 연결되었는지 확인하며 연결되었다는게 확인 될 때마다 그 노드 순번에 출력되어지게 알고리즘을 구성하려 했습니다.
내 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
import sys
read = sys.stdin.readline
def bfs(v):
q = deque() # pop메서드의 시간복잡도가 낮은 디큐 내장 메서드를 이용한다
q.append(v)
visit_list[v] = 1 # 해당 V 값을 방문처리
while q: # q가 빌때까지 돈다
v = q.popleft() # 큐에 있는 첫번째 값 꺼낸다
print(v, end=" ") # 해당 값 출력
for i in range(1, n + 1): # 1부터 N까지 돈다
if visit_list[i] == 0 and graph[v][i] == 1: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
q.append(i) # 그 i 값을 추가
visit_list[i] = 1 # i 값을 방문처리
def dfs(v):
visit_list2[v] = 1 # 해당 V값 방문처리
print(v, end=" ")
for i in range(1, n + 1):
if visit_list2[i] == 0 and graph[v][i] == 1: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
n, m, v = map(int, read().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
visit_list = [0] * (n + 1) # dfs의 방문기록
visit_list2 = [0] * (n + 1) # bfs의 방문기록
for _ in range(m):
a, b = map(int, read().split())
graph[a][b] = graph[b][a] = 1 # 입력으로부터 노드 연결 정보 저장
dfs(v)
print()
bfs(v)
참고
그래프와 방문기록을 생성할 때 어째서 이렇게 만드는 걸까?
위의 코드에서 사용되는 파이썬 자료구조의 인덱싱은 모두 0부터 시작됩니다. 그렇지만 우리가 탐색할 그래프의 노드 번호는 1부터 시작되죠.
우리가 원하는 인덱싱을 하기 위해서 이렇게 구현을 해야했던 것입니다.
다른 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# True, False 로 구현
from collections import deque
N, M, V = map(int, input().split())
graph = [[False] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
graph[a][b] = True # 입력으로부터 노드 연결 정보 저장
graph[b][a] = True
visited1 = [False] * (N + 1) # dfs의 방문기록
visited2 = [False] * (N + 1) # bfs의 방문기록
def bfs(V):
q = deque([V]) # pop메서드의 시간복잡도가 낮은 디큐 내장 메서드를 이용한다
visited2[V] = True # 해당 V 값을 방문처리
while q: # q가 빌때까지 돈다
V = q.popleft() # 큐에 있는 첫번째 값 꺼낸다
print(V, end=" ") # 해당 값 출력
for i in range(1, N + 1): # 1부터 N까지 돈다
if not visited2[i] and graph[V][i]: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면
q.append(i) # 그 i 값을 추가
visited2[i] = True # i 값을 방문처리
def dfs(V):
visited1[V] = True # 해당 V값 방문처리
print(V, end=" ")
for i in range(1, N + 1):
if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
dfs(V)
print()
bfs(V)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 정점만 저장해서 해결
from collections import deque
def dfs(start):
visited[start] = True # start 값을 방문 처리
print(start, end=" ") # 해당 값 출력
for i in graph[start]: # 해당 리스트에서 확인
if not visited[i]: # i 값을 방문하지 않았다면
dfs(i) # i 값으로 dfs를 돈다.(더 깊이 탐색)
def bfs(start):
queue = deque([start]) # pop메서드의 시간복잡도가 낮은 디큐 내장 메서드를 이용한다
visited[start] = True # start 값을 방문 처리
while queue: # 큐가 빌때까지 돈다
v = queue.popleft() # 큐에 있는 첫번째 값을 빼낸다
print(v, end=" ") # 꺼낸 값을 출력한다
for i in graph[v]: # 해당 리스트에서 확인
if not visited[i]: # i 값을 방문하지 않았다면
visited[i] = True # i 값 방문 처리
queue.append(i) # i 를 큐에 추가
N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)] # N+1 개 만큼 리스트 안에 리스트를 생성
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a) # 입력에 맞게 노드 연결 정보를 저장
# 정렬
for i in graph:
i.sort()
# dfs
visited = [False] * (N + 1)
dfs(V)
print()
# bfs
visited = [False] * (N + 1) # 방문 처리 초기화
bfs(V)