[백준 1260] DFS와 BFS - 파이썬 (DFS, BFS 개념 문제에 적용하면서 공부하기)
백준 1260 - DFS와 BFS
DFS는 깊이 우선 탐색이고, BFS는 넓이 우선 탐색이라는 개념은 알고 있지만, 막상 문제를 풀어보면 이걸 어떻게 코드로 표현해야 할지 모르겠다.
그래서 예제를 풀어보면서 이해하려고 노력했는데, 해당 문제(1260)와 dfs, bfs 개념에 대해 자세히 설명해 놓은 블로그의 도움을 많이 받았다.
이 블로그를 참고하면서 이해한 내용을 의식의 흐름대로 작성해보았다.
DFS와 BFS를 이해하기 위해서는 아래 3가지를 명심해야 한다.
1) DFS는 스택 자료구조, BFS는 큐 자료구조를 이용한다.
2) 방문한(=탐색한) 노드는 방문처리하여, 중복 탐색하지 않도록 한다.
3) 리스트(스택 또는 큐)에서 제거할 때, 제거되는 노드의 인접한 노드들 중 방문하지 않은 노드를 리스트에 넣는다.
먼저, DFS의 탐색 과정부터 살펴보겠다.
DFS는 깊이 우선 탐색으로, 하나의 방향을 정하여 끝까지 파고들어 탐색하고, 끝에 도달했다면 다시 위로 올라가서 다른 가지가 나타나는 시점부터 다시 탐색을 시작한다.
DFS는 스택 자료구조를 이용한다고 했다. 스택의 특징은 후입선출이라는 것이 핵심이다.
탐색 시작할 노드(0)를 스택에 넣는다.
해당 노드(0)를 스택에서 꺼내면서, 해야할 두가지 일이 있다. ①방문처리하기 ②방문하지 않은 인접한 노드를 스택에 담기
그러면 현재 스택에는 탐색 시작한 노드의 인접한 노드(1, 2)가 들어가 있을 것이다.
여기서 맨 위의 노드(1)를 꺼내어, 다시 ①②를 진행한다. ( → 이 부분에서, 스택 자료구조의 특징이 활용되는 것)
이렇게 되면, 나는 첫 노드와 인접한 노드들(1, 2) 중 방향을 하나 정하여(1) 탐색을 시작한 것이다.
끝까지 탐색하여, 더이상 스택에 넣을 인접한 노드가 없다면, 스택의 가장 상단에 위치한 것은 선택되지 못한 노드들 중 가장 깊은 레벨에 속하는 노드일 것이다.
그러면 또 다시, 해당 노드에 대해 ①②를 진행한다.
스택에 더이상 노드가 없을 때까지 위 과정을 반복하면 된다.
BFS의 탐색 과정을 살펴보겠다.
BFS는 넓이 우선 탐색으로, 같은 레벨에 있는 노드를 모두 탐색 후에, 다음 레벨로 넘어간다고 생각하면 된다.
BFS는 큐 자료구조를 이용한다고 했다. 큐의 특징은 선입선출이라는 것이 핵심이다.
탐색 시작할 노드(0)를 큐에 넣는다.
마찬가지로, 큐에서 꺼내면서 ①방문처리하기 ②방문하지 않은 인접한 노드를 큐에 담기
하지만 여기서, 스택과 달리 큐는 선입선출 방식이기 때문에, 먼저 들어간 노드가 출력된다.
예를 들어, 1번 노드를 큐에서 꺼냈다면, 1번 노드의 방문하지 않은 인접노드인 3, 4번이 큐에 쌓이지만, 그 다음으로 꺼내는 것은 3 or 4 가 아니라, 현재 큐에서 가장 먼저 들어온 2번 노드가 되는 것이다. 이때, 2번 노드를 꺼냄과 동시에 2번 노드의 인접한 노드(5,6)도 큐로 들어가기 때문에 같은 레벨의 노드들(3,4,5,6)이 큐에 쌓이게 된다.
즉, 큐 자료구조를 이용하면서, 인접한 노드는 뒤로 계속 쌓이게 되지만, 그 이전에 들어왔던 인접 노드들(=같은 레벨)이 먼저 출력되는 것이다.
마찬가지로, ①②과정을 더 이상 탐색할 노드가 없을 때까지 반복하면 된다.
위 내용을 참고하여, 1260번 문제를 풀면 아래와 같다.
# DFS
def dfs(idx):
Visited[idx] = True # 방문 처리
print(idx, end=" ")
for i in Nodes[idx]: # 탐색하는 노드의 인접한 노드들 중
if not Visited[i]: # 아직 방문하지 않은 노드라면
dfs(i) # 바로 그 방문하지 않은 노드에 대해 DFS 탐색
# DFS 개념을 이해하는 데 스택을 활용했던 것과 달리, 인접 노드를 리스트에 넣지 않는다는 점이 헷갈릴 수 있는데,
# 여기서는 리스트에 직접 노드를 추가하는 것 대신, 재귀함수를 활용했다고 생각하면 된다.
# 인접한 노드가 있다면 계속해서 dfs()를 실행할 것이고, 더 이상 인접한 노드가 없다면,
# 가장 최근의 for문으로 다시 돌아가 작업을 수행하기 때문이다.
# (이렇게 가장 최근의 for문으로 다시 돌아가서 dfs()를 수행하는 것을, 스택에서 가장 나중에 들어온 것을 꺼낸다는 개념으로 생각하면 좋을 것 같다.)
# BFS
def bfs(idx):
Visited_BFS[idx] = True # 방문 처리
queue = [idx] # 큐에 탐색 대상을 넣음
while queue:
v = queue.pop(0) # 큐의 선입선출 활용 (deque의 popleft()으로 대체 가능)
print(v, end=" ")
for i in Nodes[v]: # 탐색하는 노드의 인접한 노드들 중
if not Visited_BFS[i]: # 아직 방문하지 않은 노드라면
queue.append(i) # 큐에 추가
Visited_BFS[i] = True # 방문 처리
import sys
N, M, V = map(int, sys.stdin.readline().split())
# 노드 연결 정보를 담을 리스트
Nodes = [[] for _ in range(N+1)]
# 방문처리를 위한 리스트 (Visited는 DFS용, Visited_BFS는 BFS용으로 설정하였음)
Visited = [False]*(N+1)
Visited_BFS = [False]*(N+1)
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
Nodes[a].append(b)
Nodes[b].append(a)
for i in range(1, N+1):
Nodes[i].sort()
dfs(V)
print()
bfs(V)
참고
https://velog.io/@falling_star3/%EB%B0%B1%EC%A4%80Python-1260%EB%B2%88-DFS%EC%99%80BFS