말 그대로 모든 경우의 수를 탐색하는 알고리즘이다.
최댓값 혹은 최솟값을 구해야 할 때 주로 사용되는데, 선택 정렬과 어느 정도 비슷한 부분이 있는 것 같다. 완전탐색은 DFS/BFS로 수행하는데, 이때 사용되는 자료구조가 스택과 큐이다. (스택, 큐 대신 재귀로도 구현할 수 있다.)
자, 이제 하나하나 찬찬히 살펴보고 백준 실제 문제 풀이를 통해 완전탐색을 분할 정복 해보겠다. 💪
1. DFS (Depth-First Search, 깊이우선탐색)
1) DFS란?
- 임의의 노드로부터 출발해, 인접한 노드가 더이상 없을 때까지 자식 노드로 뻗어가면서 탐색하는 알고리즘이다. (인접한 노드가 여러 개인 경우, 번호가 낮은 것부터 우선적으로 탐색한다.)
- 즉, '넓게'보다는 우선 '깊게' 탐색해 보겠다는 알고리즘이다.
- 스택과 재귀함수를 통해 DFS를 구현할 수 있다. (for문으로도 구현할 수 있다.)
2) DFS를 구현해 보자!
스택 (FILO)
- 파이썬 리스트의
append()로 push를,pop()으로 pop을 하면서 스택을 통한 백트래킹을 구현할 수 있다. - 추가로, 출력하고 싶다면 (스택의 최상단부터는)
print(stack[::-1])로, (최하단 원소부터는)print(stack)으로 구현할 수 있다.
재귀함수
보통 DFS를 구현할 때 for문 대신 재귀함수를 많이 사용하는 것 같다. (아니, 많이 사용한다.)
재귀함수를 쓸 때는 반드시 유의해야 할 사항이 있다.
종료 조건을 반드시 명시한다. (안 그러면 무한루프)
함수에 대한 데이터는 스택 프레임에 저장되었다가 pop 된다. 그래서 스택을 사용해야 할 때 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많다고 한다.
아무튼 다시 DFS로 돌아와서,
스택 혹은 재귀함수를 통해 구현한 DFS의 내부 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. (번호가 가장 낮은 것부터)
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리 한다. 이때, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
이를 코드로 구현해 보면 다음과 같다.
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차원 리스트 -> 총 8개의 노드로 이뤄진 그래프)
graph = [
[], # 0번째 인덱스는 빈칸으로 둔다. (노드1 ~ 부터 시작한다.)
[2, 3, 8], # 1번 노드는 2, 3, 8번 노드와 연결되어 있다.
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문한 정보를 표현한다. (1차원 리스트)
visited = [False] * 9
dfs(graph, 1, visited)2. BFS (Breadth-First Search, 너비우선탐색)
1) BFS란?
- 임의의 노드로부터 출발해, 인접한 노드부터 우선적으로 거치고 자식으로 내려가는 알고리즘이다. (DFS와 마찬가지로 번호가 낮은 노드부터 탐색한다.)
- 즉, '깊게'보다는 우선 '넓게' 탐색하겠다는 것이다.
- DFS가 스택을 통해 구현한다면, BFS는 큐를 이용하여 구현한다.
2) BFS를 구현해 보자!
큐 (FIFO)
- 파이썬 리스트의
append()로 push를,popleft()로 pop을 수행한다. - 스택과 달리 큐는 선입선출(First In First Out)이므로, 들어온 순서대로 백트래킹 된다.
큐를 통해 구현한 BFS의 구체적인 동작 과정은 다음과 같다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
이를 코드로 구현해 보면 다음과 같다.
from collections import deque
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리를 사용한다.
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)
visited[i] = True
# 각 노드가 연결된 정보를 표현한다. (2차원 리스트 -> 총 8개의 노드로 이뤄진 그래프)
graph = [
[], # 0번째 인덱스는 빈칸으로 둔다. (노드1 ~ 부터 시작한다.)
[2, 3, 8], # 1번 노드는 2, 3, 8번 노드와 연결되어 있다.
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문한 정보를 표현한다. (1차원 리스트)
visited = [False] * 9
bfs(graph, 1, visited)
+ 추가 : deque 라이브러리
- 파이썬은 유용한 자료구조 라이브러리로 collections 라이브러리를 제공한다.
- deque 라이브러리는 이 중에서도 '큐' 자료구조를 제공하는 라이브러리이다.
(Queue 라이브러리가 있는데, 큐를 구현하는 라이브러리가 아니라고 한다.) - list 대신 왜 deque 라이브러리를 사용할까? → 바로 더 효율적인 시간복잡도 때문이다.
- 가장 앞쪽/뒤쪽 원소 추가 :
appendleft(x)/append(x)-> deque는 모두 O(1)이다. (리스트는 O(n), O(1)) - 가장 앞쪽/뒤쪽 원소 제거 :
leftpop()/pop()-> deque는 모두 O(1)이다. (리스트는 O(n), O(1)) - 따라서, deque는 원소 추가 혹은 제거에 있어서 상당히 효율적이다.
- 다만, 리스트와 달리 deque는 인덱싱/슬라이싱은 사용할 수 없다고 한다.
💡학습 소감
- 원리는 이해 된다. 다만, 코드로 구현이 되지 않을 뿐.. 코드의 큰 틀을 가지고 알고리즘 문제에 연습을 많이 해봐야 겠다. (23.04.12)
