dfs와 bfs는 여러가지 방법으로 구현될 수 있습니다. 예를 들면, 인접행렬과 인접리스트를 사용하는 것으로 나눌 수 있고, dfs에서는 스택자료구조르 만들어 사용하는 것과 재귀함수를 이용하는 방법으로 구현하는 방식으로도 나뉠 수 있습니다. 그래프 탐색을 처음 공부할 때, 내가 모르는 형태의 구현방법으로 적힌 다른 사람들의 풀이를 보고 어려움을 느낀 점이 많아 포스팅으로 남겨봅니다.
이 글에서는 각각의 방법을 직접 구현해보고, 장점과 단점에 대해서 이야기해보겠습니다. 이 글을 작성하기 위해서 백준 1260 dfs와 bfs 문제를 활용하겠습니다.
인접리스트와 인접행렬은 그래프를 코드 상에서 표현하는 방식입니다. 아래의 그림으로 나타내어지는 그래프를 살펴보겠습니다.
이 그래프를 인접 행렬로 나타낸 것은 아래와 같습니다.
graph = [[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]]
graph = [
[1, 2, 3],
[0, 3],
[0, 3],
[0, 1, 2]
]
dfs와 bfs를 구현하고 경로를 출력하는 문제입니다.
dfs를 아래의 4가지 방법으로 구현해보겠습니다.
n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
def dfs(matrix, i, visited):
stack=[i]
while stack:
value = stack.pop()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for c in range(len(matrix[value])-1, -1, -1):
# 문제에서 작은 숫자부터 입력하기를 요구해서 반대로 순회했습니다.
# 순차적으로 하면 스택에 2,3,4 순으로 입력되고 4부터 pop되어
# 가장 큰 수인 4부터 pop되기 때문입니다.
if matrix[value][c] == 1 and not visited[c]:
stack.append(c)
dfs(matrix, v, visited)
n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
def dfs(matrix, i, visited):
visited[i] = True
print(i, end=' ')
for c in range(len(matrix[i])):
if matrix[i][c] == 1 and not visited[c]:
dfs(matrix, c, visited)
dfs(matrix, v, visited)
n, m, v = map(int, input().split())
graph = [[]] * (n+1)
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
if graph[f] == []:
graph[f] = [t]
else:
graph[f].append(t)
if graph[t] == []:
graph[t] = [f]
else:
graph[t].append(f)
def dfs_stack(graph, i, visited):
stack = [i]
visited[i] == True
while stack:
value = stack.pop()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for j in graph[value]:
if not visited[j]:
stack.append(j)
for i in graph: # 앞서 인접행렬에서 거꾸로 순회했던 이유가 같습니다.
i.reverse()
dfs(graph, v, visited)
n, m, v = map(int, input().split())
graph = [[]] * (n+1)
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
if graph[f] == []:
graph[f] = [t]
else:
graph[f].append(t)
if graph[t] == []:
graph[t] = [f]
else:
graph[t].append(f)
def dfs(graph, i, visited):
visited[i] = True
print(i, end=' ')
for j in graph[i]:
if not visited[j]:
dfs(graph, j, visited)
dfs(graph, v, visited)
bfs를 아래의 2가지 방법으로 구현해보겠습니다.
n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
from collections import deque
def bfs(matrix, i, visited):
queue= deque()
queue.append(i)
while queue:
value = queue.popleft()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for c in range(len(matrix[value])):
if matrix[value][c] == 1 and not visited[c]:
queue.append(c)
n, m, v = map(int, input().split())
graph = [[]] * (n+1)
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
if graph[f] == []:
graph[f] = [t]
else:
graph[f].append(t)
if graph[t] == []:
graph[t] = [f]
else:
graph[t].append(f)
from collections import deque
def bfs(graph, i, visited):
queue= deque()
queue.append(i)
while queue:
value = queue.popleft()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for j in graph[value]:
queue.append(j)
bfs(graph, v, visited)