탐색은 자주 등장하는 코딩 테스트 유형으로, 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 그래프나 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다.
이 두 탐색 알고리즘을 위한 기본 자료구조 스택과 큐는 이 링크에 설명하였다.
DFS와 BFS를 이해하기 위한 재귀함수는 이 링크에 설명하였다.
그래프 탐색
DFS와 BFS 알고리즘 모두 그래프에서의 탐색을 수행하는 알고리즘이기 때문에, 그래프의 기본 개념에 대해 짚고 넘어가보자!
그래프는 노드(정점), 간선으로 표현된다. 그래프 탐색은 한개의 시작 노드에서 다수의 노드를 방문하는 것이다. 간선으로 연결된 두 노드를 인접하다고 표현한다. 그리고 간선에는 보통 cost가 추가로 주어진다. 쉽게 간선은 도로, 노드는 도시 라고 생각하면 된다. 위의 그림을 코드로 표현하는 방법에는 인접 행렬, 인접 리스트가 있다.
그래프 표현 with 인접행렬
2차원 배열로 그래프의 연결 관계를 표현하는 방식이다. 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. python에서는 2차원 리스트로 아래와 같이 표현 가능하다.
INF=999999
graph=[
[0,7,5],
[7,0,INF],
[5,INF,0]
]이는 다음과 같이 2차원 배열로 표현한 것이다.
그래프 표현 with 인접리스트
인접 리스트 방식에서는 모든 노드의 연결 정보를 다음과 같이 차례로 연결하여 저장한다. 인접 리스트는 '연결 리스트' 라는 자료형으로 구현해야한다. Java C++은 연결 리스트를 구현하기 위한 표준 라이브러리를 제공한다. 하지만, 파이썬은 그냥 기본 자료형 쓰면 된다.
파이썬의 기본 자료형 리스트 자료형은 append()와 메소드를 제공하며 연결리스트의 기능을 모두 제공한다. 파이썬으로 인접리스트를 이용해 그래프를 표현할때도 2차원 리스트를 이용하면 된다.
graph=[[]for_ in range(3)]
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
위의 2차원 배열 graph는 아래와 같은 그림을 나타낸다.
📌두 방식의 차이
메모리와 속도 측면에서 비교해보면,,,
| - | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 메모리 | 많이 소모 | 적게 소모 |
| 속도 | 빠름 | 느림 |
위와 같은 결과가 나오는 이유는, 먼저, 인접 행렬은 연결되어있지 않은 노드도 그래프 행렬에 추가하기 때문에 (ex.graph[1][2]와 같은) 메모리를 더 많이 소모하고, 인접 리스트 방식은 연결된 데이터를 하나하나 확인해봐야 하기 때문에 인접행렬에 비해 느리다.
DFS
Depth-First Search. 깊이 우선 탐색이라고 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 이 알고리즘은 특정 경로로 탐색하며 최대한 깊숙이 들어가 노드를 방문하고 다시 돌아와서 다른 경로로 탐색하는 알고리즘이다. DFS는 stack 자료구조를 이용하며 동작과정은 아래와 같다.
- 탐색 시작 노드를 스택에 삽입, 방문처리
2-1. 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드 있으면, 스택에 넣고 방문 처리.
2-2. 스택의 최상단 노드에 인접한 노드 중 방문하지 않은 노드 없으면, 스택에서 최상단노드 뺌.
- 2-1과 2-2를 다시 수행 못할 때까지 반복
방문 처리는 스택에 한번 삽입된 노드가 다시 삽입되지 않게 체크하는 것이다. (각 노드당 1회) 여기서, 만약 인접한 노드 중 방문하지않은 노드가 여러개 있다면, 번호가 낮은 순부터 방문하는게 관행이라고 한다. 직접 그래프가 동작하게 되는 과정을 한번 보자.(손글씨 주의)
이 그래프에 DFS 탐색 알고리즘을 적용했다.
인접한 노드가 여러개인 경우 더 작은 숫자를 고르고, 최상단 노드를 중점으로 동작하는 것을 확인할 수 있다. 위의 그래프를 깊이를 우선시해 6까지 먼저 깊이 들어간 후, 다시 7노드로 돌아와 8번 노드를 방문하고, 그 후에 3번 노드를 차례로 방문하는 것을 확인할 수 있다. 결국 경로는 1→2→7→6→8→3→4→5 순으로 방문하는 것을 확인할 수 있다. 이를 재귀함수를 이용해 구현가능하다.
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[v]를 순회하며 재귀방문)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited=[False]*9 # 9개의 노드 모두 미방문 처리로 선언 및 초기화
DFS(graph,1,visited) # 1번 노드를 시작노드로 하여 DFS 알고리즘 작동
BFS
Breadth-First Search. 너비 우선 탐색이라고 불리며, 그래프에서 인접한 노드를 먼저 탐색하는 방법이다. 시작 노드에서 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용한다. 먼저 들어온 노드가 먼저 나가기 때문에 자연스럽게 가까운 노드부터 탐색한다. BFS의 동작과정은 아래와 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입 후 방문처리
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복
이 그래프에 BFS 탐색 알고리즘을 적용했다.
자료구조 큐를 사용했기 때문에, 먼저 방문한 노드가 빠져나가 해당 노드에 인접한 노드들이 모두 들어오기 때문에 깊이가 아닌 너비로 탐색하는 것을 알 수 있다. 처음에 1과 인접한 노드 2,3,8이 한번에 들어간다. DFS의 경우 재귀함수로 스택을 구현하기 때문에, 2번 노드 방문 시 인접한 7번 노드를 이어서 방문하기 때문에 깊이탐색을 진행했었다. BFS 는 deque 라이브러리를 사용해서 구현 가능하다.
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[v]:
queue.append(i) # 방문처리가 되지않은 노드는 모두 queue에 enque
visited[i]=True # queue에 들어간 노드는 모두 방문처리
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) # 1번 노드를 시작노드로 하여 BFS 알고리즘 수행