탐색(Search)이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS/BFS 알고리즘을 공부하기에 앞서 반드시 짚고 넘어가야 할 자료구조들에 대해서 알아보자.
자료구조
자료구조(Data Structure)란, 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.
1. 스택(Stack)
택배 트럭에 박스를 적제한 후 배달을 한다고 가정해보자.
처음 들어가는 택배들은 택배 트럭에 가장 안 쪽에 위치하게 될 것이고, 결국에는 가장 마지막에 빠져나오게 될 것이다. 이처럼 스택(stack)은 선입후출(First In Last Out) 구조이며, 공병인가?
우리가 흔히 먹는 프링글스 통처럼 입구와 출구가 동일한 형태로 시각화하면 이해하기 쉽다.
stack = []
stack.append(5) # 5 삽입
stack.append(2) # 2 삽입
stack.append(3) # 3 삽입
stack.append(7) # 7 삽입
stack.pop() # 7 삭제
stack.append(1) # 1 삽입
stack.append(4) # 4 삽입
stack.pop() # 4 삭제
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
#결과
#[5, 2, 3, 1]
#[1, 3, 2, 5]파이썬에서 스택을 구현할 때는 별도의 라이브러리를 사용할 필요가 없다. 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다. append()와 pop()의 시간복잡도는 O(1)로 매우 간단하다.
2. 큐(Queue)
번호표를 뽑아 대기줄을 서서 음식점에 들어가 밥을 먹는다고 가정해보자
새치기는 이루어지지 않고 먼저 온 순서대로 음식점에 들어가 식사를 하게 될 것이다. 이처럼 큐(queue)는 선입선출(First In First Out) 구조이며,
공장의 제조벨트를 생각하여 시각화를 하면 이해하기 쉽다.
from collections import deque
queue = deque()
queue.append(5) # 5 삽입
queue.append(2) # 2 삽입
queue.append(3) # 3 삽입
queue.append(7) # 7 삽입
queue.popleft() # 5 삭제
queue.append(1) # 1 삽입
queue.append(4) # 4 삽입
queue.popleft() # 2 삭제
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
# 출력
# deque([3, 7, 1, 4])
# deque([4, 1, 7, 3])파이썬에서는 collections 모듈에 있는 deque()를 활용해서 큐를 구현할 수 있다. 리스트를 활용하여 구현해낼 수도 있지만, deque()를 활용하는 것이 훨씬 효율적이다.
3. 재귀함수(Recrusive function)
재귀 함수는 자기 자신을 그대로 호출하는 함수이다.
재귀 함수의 수행은 스택(stack) 자료구조를 이용하는 것과 같다. 함수를 호출했을 때 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 또한, 재귀함수를 활용하게 되면 반복문의 활용을 대체할 수 있게 된다. 팩토리얼을 구현하는 과정을 예시로 들어보면 다음과 같다.
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
return n * factorial_recursive(n-1)
#각각의 방식으로 구현한 n! 출력
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
# 출력
# 반복적으로 구현: 120
# 재귀적으로 구현: 120재귀함수를 활용하면 코드도 간결해지는 것뿐만 아니라, 우리가 알고있는 수학적 점화식을 그대로 사용할 수 있다. 하지만 다른 사람이 이해하기에 어려운 코드가 될 수도 있으므로 신중하게 사용해야 한다.
DFS
깊이 우선 탐색(Depth-First Search)이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
깊이 우선 탐색 알고리즘은 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 되돌아가 다른 경로로 탐색하는 알고리즘이다.
DFS는 스택(stack) 자료구조(혹은 재귀함수) 를 이용하며 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
방문 처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미하며 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다. 각 노드에 인접 노드가 여러 개일 경우 방문 기준을 정하는 것이 중요하다. (예. 번호가 낮은 인접노드부터)
과정을 작성해보자면,
-> 시작노드 1을 스택에 쌓고 방문 처리한다.
-> 최상단 노드인 1에 인접 노드 중 번호가 낮은 2를 스택에 쌓고 방문 처리한다.
-> 최상단 노드인 2에 인접 노드 중 방문하지 않은 노드인 7을 스택에 쌓고 방문 처리를 한다.
-> 최상단 노드인 7에 인접 노드 중 번호가 낮은 6을 스택에 쌓고 방문 처리를 한다.
-> 최상단 노드인 6에 방문하지 않는 인접노드가 없으니 스택에서 6을 꺼낸다.
-> 최상단 노드인 7에 인접 노드 중 방문하지 않은 노드인 8을 스택에 쌓고 방문 처리한다.
위와 같은 방법으로 진행하다 보면 남아있는 노드에 방문하지 않은 노드가 없게 되고, 탐색 순서를 보면 1,2,7,6,8,3,4,5임을 알 수 있다.
# DFS
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v] = True
print(v, end=" ")
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[], # 노드가 1번부터 시작하기 때문에 비워둔다. index 0
[2, 3, 8], # 1번 노드와 인접한 노드 index 1..
[1, 7], # 2번 노드와 인접한 노드
[1, 4, 5], # 3번 노드와 인접한 노드...
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 인덱스 0 을 포함해 9개 초기화
# 정의된 DFS 함수 호츌
dfs(graph, 1, visited)
# 출력 : 1 2 7 6 8 3 4 5 BFS
너비 우선 탐색(Breadth First Search)이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와 반대이다. 최단거리 문제에서 자주 사용된다.
BFS에서는 큐(queue) 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣으면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
같은 그래프를 이용해 과정을 작성해보자면,
-> 시작 노드인 1을 큐에 넣고 방문 처리를 한다.
-> 큐에서 노드 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8 을 모두 큐에 넣고 방문 처리를 한다.
-> 큐에서 노드 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 넣고 방문 처리를 한다.
-> 큐에서 노드 3을 꺼내고 방문하지 않은 인접 노드 4와 5를 모두 큐에 넣고 방문 처리를 한다.
-> 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.
-> 큐에서 노드 7을 꺼내고 방문하지 않은 인접 노드 6을 큐에 넣고 방문 처리를 한다.
남아 있는 노드에 방문하지 않은 인접 노드가 없게 되고,노드의 탐색 순서는 1,2,3,8,7,4,5,6이다. 각 노드 간의 거리를 1이라고 하면, 1,2,3,8은 시작노드 1로부터 거리가 1이고 7,4,5는 거리가 2이다. 마지막으로 6은 거리 3임으로 가까운 거리의 노드부터 탐색되었다는 것을 보여준다.
from collections import deque
# BFS
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]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
# 출력 : 1 2 3 8 7 4 5 6 