DFS와 BFS에 들어가기 전에
DFS, BFS 알고리즘은 코딩 테스트의 대표적인 탐색 문제 유형이다.
이를 제대로 이해하기 위해서는 스택과 큐에 대한 사전지식이 전제되어야 한다.
스택과 큐는 자료구조에서 핵심적인 개념으로, 삽입(Push)과 삭제(Pop)로 구성된다.
이 외에도 수용가능한 크기를 넘어서는 상태에서 데이터가 삽입되는 오버플로, 비어있는 데이터에 삭제연산을 수행하여 발생하는 언더플로 등을 고려해주어야 한다.
스택
박스쌓기로 비유하면 편하다. 가장 최근에 쌓은 박스가 가장 먼저 빠진다. (후입선출)
명령어는 빈 배열에서 삽입 시 append(), 삭제 시 pop()를 사용한다. 리스트의 가장 뒤 쪽에서 데이터를 삽입(순방향)하고, 가장 뒤 쪽에서 데이터를 꺼낸다.
큐
큐는 역방향으로 데이터를 쌓는다. 쌓인 순으로 삭제되는 선입선출 구조를 갖고 있다.
파이썬에서 큐를 구현하기 위해서는 collections 모듈에서 제공하는 명령어를 활용한다.
list(que) 메서드를 이용하여 deque객체를 리스트 자료형으로 변환할 수 있다.
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.popleft()
재귀함수
선언한 함수 안에 본인을 다시 호출시키는 함수이다. 최대 깊이(용량)를 초과하면 자동으로 정지된다. 그러나 이렇게 루프가 끝까지 돌도록 방지하지 않고, 종료 조건을 꼭 명시해주어야 한다.
재귀함수는 내부적으로 스택 자료구조와 동일하다. 따라서 상당수 알고리즘은 재귀함수를 이용해 간편하게 구현할 수 있다.
일반 반복문보다 코드가 더 간결하다는 이점이 있다. 이는 수학의 점화식을 따랐기 때문인데, 이후 배울 다이나믹 프로그래밍에서도 중요하니 용어와 개념을 꼭 기억하고 있으면 좋을 듯 하다.
DFS
DFS는 깊이 우선 탐색 알고리즘이라고도 하며, 특정한 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색한다. 탐색을 수행함에 있어 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.
탐색은 간선을 통해 노드를 방문하는 방식으로 이루어지는데, 이 때 노드와 간선으로 구성된 맵을 그래프라고 한다. 파이썬에서 그래프를 표현하는 방법은 크게 두 가지로, 인접행렬과 인접리스트 방법이다.
이 때 '인접하다'는 개념은 한 개의 간선으로 연결되어 있는 노드들을 의미한다.
그 중 가장 흔하게 사용되는 인접행렬 방식의 예제 코드이다.
INF = 999999999
graph = [
[0,7,5]
[7,0,INF]
[5,INF,5]
]DFS의 구체적인 동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 모든 인접 노드를 방문했다면 스택에서 최상단 노드를 꺼낸다. 꺼내는 경우 직전의 노드로 돌아가게 된다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
#DFS Method
def dfs(graph,v,visited):
visited[v] = True
print(v,end='')
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph,1,visited)
>> 1 2 7 6 8 3 4 5
BFS
너비 우선 탐색 알고리즘으로, 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와 달리 가장 가까운 노드부터 탐색하는 알고리즘이다.
BFS 알고리즘 구현에는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석적이다.
BFS의 구체적인 동작 과정
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
# BFS Method
from collections import deque
def bfs(graph, start, visited):
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
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)
정리하며
코딩 테스트 문제 유형 중 2차원 배열에서의 탐색 문제를 만나면 위와 같이 그래프 형태로 바꿔 생각하면 훨씬 쉽게 접근할 수 있다.
DFS 알고리즘은 스택 자료구조를 활용하여 재귀 함수로 구현하고,
BFS 알고리즘은 큐 자료구조를 활용하여 import된 모듈을 통해 구현한다.
