[Algorithm] 탐색(DFS & BFS)
Intro
탐색 챕터이다. DFS, BFS의 경우는 정보처리기사를 공부하면서 이론적으로는 알고 있었지만 알고리즘 구현은 하지 못해보았다. 개념과 알고리즘 풀이를 해보려 한다.
그래프
탐색을 알기 전에 그래프 구조를 알아야 한다. 그래프는 노드와 간선으로 구성되어 있다.
쉽게 설명하자면 노드는 도시이며 간선은 도로라고 생각하면 된다. 각 노드에서 이동할 때 간선을 타고 다른 노드로 이동하는데 이를 도식화 한 것이 그래프이다.
인접 행렬 & 인접 리스트
인접 행렬이란, 2차원 배열로 그래프의 연결 관계를 표현하는 방식이다.
인접 리스트란, 리스트로 그래프의 연결 관계를 표현하는 방식이다.
2개의 차이점은 인접 행렬의 경우는 모든 관계를 표현하지만, 인접 리스트는 연결된 관계만 표현한다.
DFS
DFS(Depth-First Search)란, 깊은 부분을 우선적으로 탐색하는 깊이 탐색 알고리즘으로, 노드를 방문한 후에 다른 경로를 탐색한다.
구체적인 동작으로는
- 탐색 시작 노드를 스택에 삽입하고, 방문 처리를 한다.
- 스택의 최상단 노드에서 방문하지 않은 노드가 하나라도 있으면, 노드를 스택에 넣고 방문처리한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번 과정이 수행되지 않을 때까지 반복한다.
만약, 2번 동작에서 방문하지 않은 노드가 여러 개라면 번호가 낮은 순서부터 처리한다.
DFS는 스택의 최상단 노드를 꺼내서 작업을 하기에 스택 자료구조를 사용하며 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.
DFS 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# dfs 메서드 정의
# 파라미터 : 그래프, 현재노드(v), 방문여부
# graph = [리스트] -> 1번 노드를 기준으로 인접한 노드번호를 넣어줌. 0번인덱스는 [] 빈 리스트 담기
# 그래프 변수에 2차원 리스트를 통해 노드가 연결된 정보를 표현한다.
graph = [[], [2, 3, 8], [1,7], [1,4,5], [3,5], [3,4],[7],[2,6,8],[1,7] ]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
# 재귀함수를 통해 현재노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
# 방문하지 않은 노드들만 방문
if not visited[i]:
#재귀 함수를 통해 처리
dfs(graph, i, visited)
BFS
BFS(Breadth-First Search)란, 너비 우선 탐색으로 불리며, DFS와 달리 가장 가까운 노드부터 탐색하는 알고리즘이다.
BFS는 가까운 노드부터 처리하기에, 선입선출 방식인 큐 자료구조를 사용한다.
구체적인 동작으로는
- 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번 과정이 수행되지 않을 때까지 반복한다.
만약, 2번 동작에서 방문하지 않은 노드가 여러 개라면 번호가 낮은 순서부터 처리한다.
BFS 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Breath First Search (BFS) 알고리즘
# -> 가장 가까운 노드들부터
from collections import deque
# graph 변수에 인접한 노드 정보를 저장
graph = [[], [2, 3, 8], [1,7], [1,4,5], [3,5], [3,4],[7],[2,6,8],[1,7] ]
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
visited[start] = True
while queue:
#popleft -> deque 앞의 값 삭제 후 반환 / pop -> deque 뒤쪽 값 삭제
# 큐 자료구조의 맨 앞의 값을 꺼내는 작업
v = queue.popleft()
print(v, end='')
for i in graph[v]:
# 꺼낸 v 노드의 인접한 값들 중 방문하지 않은 값들을 큐에 넣어줌.
if not visited[i]:
queue.append(i)
# 방문 처리
visited[i] = True
visited = [False] * 9
bfs(graph, 1, visited)
정리
DFS -> 깊이 우선 탐색, 스택 자료구조 사용
BFS -> 너비 우선 탐색, 큐 자료구조 사용