알고리즘[Algorithm] | DFS & BFS

DFS/BFS를 알아가기 전에..

탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정이며 DFS/BFS가 이 알고리즘에 속한다.

DFS/BFS를 풀기 위해서 알아야 할 몇 가지 자료구조를 먼저 알아보려고 한다.

 

여기서 자료구조란 데이터를 표현, 관리, 처리하기 위한 구조이다.

자료구조 중에서 스택과 큐가 가장 기초적인 개념으로 자리잡고 있다.

 

스택(Stack)

나중에 들어온 데이터가 먼저 삭제되는 후입선출 구조의 자료구조이다.

예전 블로그에서 실행 컨텍스트에 대해 개념을 정리하면서 스택/큐 개념도 함께 정리했는데, 당시 그렸던 그림을 첨부한다.

 

 

그림처럼 후입 선출임을 알 수 있다.

 

이를 코드로 구현하려면 입력은 리스트의 가장 뒤쪽에 데이터를 삽입하는 append(),

출력은 리스트의 가장 뒤쪽에 있는 데이터를 꺼내는 pop()을 이용하여 작성한다.

 

stack = []

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

print(stack) # [1, 2, 3, 4, 5]

stack.pop()
stack.pop()

print(stack) # [1, 2, 3]

 

자기 자신을 다시 호출하는 함수인 재귀함수가 내부적으로 스택 자료구조와 동일하다.

 

큐(Queue)

스택과 반대로 먼저 들어온 데이터가 먼저 삭제되는 선입선출 구조의 자료구조이다.

역시나 그림을 첨부한다.

 

 

이를 코드로 구현하려면 입력은 스택과 동일하게 append()를 사용하고,

출력은 popleft()를 사용하는데 이는 collections라는 모듈의 deque를 사용해야 쓸 수 있다.

 

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

print(list(queue)) # [1, 2, 3, 4, 5]

queue.popleft()
queue.popleft()

print(list(queue)) # [3, 4, 5]

 

deque가 리스트에 비해 데이터를 넣고 빼는 속도가 효율적이기 때문에 사용한다고 한다.

 

DFS(깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

여기서 그래프는 노드(Node, 정점(Vertex)이라고도 불린다.)와 간선(Edge)으로 표현된다.

그래프 탐색은 하나의 노드에서 시작하여 여러 개의 노드를 방문하는 것이며, 노드와 노드가 간선으로 연결되어 있을 시 인접한다고 표현한다.

 

1. 인접 행렬

2차원 배열에 각 노드가 연결된 형태를 저장한다.

파이썬에서는 2차원 리스트로 구현하며, 연결되어있지 않은 노드는 999999999와 같은 큰 값으로 초기화 한다.

INF = 999999999

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

 

2. 인접 리스트

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

이때에도 2차원 리스트로 구현한다.

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0, 5))

print(graph)

 

인접 행렬 방식은 모든 관계를 저장하기 때문에 노드 개수가 많다면 메모리가 불필요하게 낭비되는데,

인접 리스트 방식은 연결된 정보만 저장하여 메모리를 효율적으로 사용할 수 있다.

 

다만, 모든 관계를 저장하는 인접 행렬 방식은 두 노드가 연결되어 있는지 확인하는 속도가 빠르며,

인접 리스트 방식은 하나하나 확인해야 하기 때문에 속도가 느리다.

 

스택 자료구조와 재귀 함수를 이용하는 DFS의 동작 과정은 아래와 같다.

 

1. 시작 노드를 스택에 삽입한 뒤 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 해당 인접 노드를 스택에 넣고 방문처리를 한다.
3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
4. 위 과정을 수행할 수 없을 때까지 반복한다.

 

BFS(너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘이다.

큐 자료구조를 이용하는 BFS의 동작 과정은 아래와 같다.

 

1. 시작 노드를 큐에 삽입한 뒤 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문처리를 한다.
3. 위 과정을 수행할 수 없을 때까지 반복한다.

---

[코드 출처]