출처: 백준 온라인 저지
https://www.acmicpc.net/problem/1260
풀이 과정
완전 탐색 문제들을 풀던 중 백트래킹 문제에서 막혔다. 백트래킹은 DFS + 가지치기인데, DFS 구현 자체를 못했기 때문이다. 그래서 우선 BFS와 DFS를 포함한 그래프 탐색 문제들을 풀기로 했다.
이 문제는 백준에 있는 가장 기본적인 BFS/DFS 문제다. BFS/DFS를 어떻게 활용하는 문제가 아니라, DFS/BFS를 구현하는 것 자체가 문제의 전부다.
자료구조에 대한 내용들을 복습하고, 다른 사람들의 풀이를 참고하여 겨우 코드를 완성했다. 그런데 테스트를 돌렸을 때 BFS 알고리즘은 결과가 잘 나왔지만, DFS 알고리즘은 그렇지 않았다.
잘못된 풀이와 그 이유
from sys import stdin
from collections import deque
n, m, v = map(int, stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
dfs_visited = [False] * (n + 1)
bfs_visited = [False] * (n + 1)
# DFS에서 낮은 숫자를 먼저 탐색하도록 역순으로 정렬
for i in graph:
i.sort(reverse=True)
# dfs 알고리즘
stack = deque()
stack.append(v)
dfs_visited[v] = True
while stack:
current = stack.pop()
print(current, end=' ')
for vertex in graph[current]:
if not dfs_visited[vertex]:
stack.append(vertex)
dfs_visited[vertex] = True
print('')
# BFS에서 낮은 숫자를 먼저 탐색하도록 정순으로 정렬
for i in graph:
i.sort()
# bfs 알고리즘
queue = deque()
queue.append(v)
bfs_visited[v] = True
while queue:
current = queue.popleft()
print(current, end=' ')
for vertex in graph[current]:
if not bfs_visited[vertex]:
queue.append(vertex)
bfs_visited[vertex] = True
위 코드에서 DFS 알고리즘이 제대로 작동하지 않은 이유는 다음과 같다.
(그림판으로 급하게 그려서 그림 상태가 좋지 않다.)
위와 같은 그래프를 위의 dfs 알고리즘 코드로 순회한다고 해보자. 첫 노드는 1이므로, for vertex in graph[current] 반복문에서 1과 연결된 노드들이 모두 스택에 저장된다. 앞에서 거꾸로 정렬을 시켰으므로 4, 3, 2 순서로 들어간다. 스택은 후입선출(LIFO)이므로 다음으로는 2가 나온다. DFS에서는 깊이 우선이므로, 원래는 노드 4를 스택에 넣은 뒤, 바로 다음으로 노드 4를 꺼내야 한다. 그런데 스택 4는 이미 스택에 저장되어 있으므로 저장이 되지 않고, 2 다음으로는 노드 3이 꺼내지게 된다.
이 문제를 해결하기 위해서는 현재 노드 A에서 인접한 노드 B를 탐색한 뒤, A에 인접한 다른 노드를 탐색하기 전에 B에 인접한 노드들을 모두 돌아야 한다. 이를 구현하는 쉬운 방법은 재귀 함수를 이용하는 것이다. 재귀 함수를 이용하면 스택을 사용하지 않고도 DFS 알고리즘을 구현할 수 있다.
재귀 함수로 구현한 DFS
from sys import stdin
dfs_visited = [False] * (n + 1)
def dfs(some_graph, visited, node):
visited[node] = True
print(node, end=' ')
for i in some_graph[node]:
if not visited[i]:
dfs(some_graph, visited, i)이 코드가 아까 본 그래프에서 어떻게 작동하는지 살펴보자. 1에서 시작한 탐색은 2를 인자로 가지는 DFS 함수를 호출하고, 이는 이어서 4, 3을 인자로 가지는 DFS 함수를 호출한다. 3에서는 방문하지 않은 인접 노드가 없으므로 이전 함수로 돌아가고, 계속 돌아가서 다시 1까지 온다. 1에서는 방문하지 않은 인접 노드가 없으므로 탐색을 마친다.
이전의 문제가 해결되었음을 알 수 있다.
BFS 알고리즘도 함수로 다시 만들고 정리한 최종 코드는 아래와 같다.
최종 풀이
from sys import stdin
from collections import deque
def dfs(some_graph, visited, node):
visited[node] = True
print(node, end=' ')
for i in some_graph[node]:
if not visited[i]:
dfs(some_graph, visited, i)
def bfs(some_graph, visited, node):
queue = deque()
queue.append(node)
visited[node] = True
while queue:
current = queue.popleft()
print(current, end=' ')
for i in graph[current]:
if not visited[i]:
queue.append(i)
visited[i] = True
n, m, v = map(int, stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
dfs_visited = [False] * (n + 1)
bfs_visited = [False] * (n + 1)
for adj_list in graph:
adj_list.sort()
dfs(graph, dfs_visited, v)
print('')
bfs(graph, bfs_visited, v)