"그래프 이론 - DFS/BFS"는 대표적인 탐색 알고리즘인 Depth First Search(DFS)와 Breath First Search(BFS) 알고리즘에 대한 글이며 """ 이것이 취업을 위한 코딩 테스트다 with 파이썬 """ 책을 바탕으로 정리한 글입니다.
0. Definition
DFS와 BFS에 대해 알기 위한 몇 가지 사전적인 개념부터 살펴보고자 합니다.
▶탐색
탐색은 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미합니다.
▶자료구조(Data Structure)
자료구조는 데이터를 표현하고 관리하고 처리하기 위한 구조입니다.
자료구조의 기초 개념으로는 스텍(stack)과 큐(queue)가 존재하며 다음 두 가지의 핵심적인 함수로 구성되어 있습니다.
- 삽입(push): 데이터 삽입
- 삭제(pop): 데이터 삭제
▶스텍(Stack)
스텍은 쌓아올린다는 것을 의미합니다.
예를 들어, 책이나 박스는 아래에서부터 위로 차곡차곡 쌓아 올립니다. 하지만, 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 합니다. 이러한 구조를 선입후출(First In Last Out) 구조 또는 후입산출(Last In First Out) 구조라고 합니다.
※ append() & pop()
파이썬으로는 append()와 pop() 메서드로 쉽게 구현이 가능합니다.
stack = []
# 삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack)
print(stack[::-1])- append()는 리스트의 가장 뒤쪽에 데이터를 삽입합니다.
- pop()는 리스트의 가장 뒤쪽에서 데이터를 꺼냅니다.
▶큐(Queue)
큐(Queue)는 줄을 서서 기다리는 것으로 생각하면 될 것 같습니다.
예를 들어, 놀이공원에서 먼저 온 사람은 먼저 들어가야 하며 나중에 온 사람일수록 나중에 들어가야 합니다. 이와 같은 경우를 "선입선출(First In First Out)"이라고 합니다.
※ deque
파이썬(python)으로 큐를 구현할 때 collections 모듈에서 제공하는 deque 자료구조를 활용하는 것을 추천합니다.
deque 자료구조는 스텍과 큐의 장점을 모두 채택한 것으로 데이터를 넣고(push), 빼는(pop) 속도가 리스트 자료형에 비해 효율적입니다.
from collections import deque
queue = deque()
## 삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제() -> 삽입(1) -> 삽입(4) -> 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue)
print(list(queue)) ## 리스트 타입으로 변경
queue.reverse()
print(queue)
print(list(queue)) ## 리스트 타입으로 변경
▶재귀함수(Recursive Function)
재귀함수는 자기 자신을 다시 호출하는 함수입니다.
재귀함수의 경우,
재귀함수가 언제 끝날지, 종료 조건을 꼭 명시해줘야 합니다. 종료 조건을 명시하지 않을 경우, 함수가 무한 호출될 수 있습니다.
다음 두 가지 예시를 들어보겠습니다.
[Ex1] 재귀 함수를 사용하지 않은 경우
def factorial_1(n):
answer = 1
for i in range(1,n+1):
answer *= i
return answer[Ex2] 재귀 함수를 사용한 경우
def factorial_2(n):
if n<=1: ## n이 1 이하인 경우는 더 이상 재귀함수를 호출하지 않음.
return 1
return n * factorial(n-1)코드가 더 간결해지는 것을 확인할 수 있습니다.
지금까지 살펴본 개념(definition)을 바탕으로 Depth First Search(DFS) 알고리즘과 Breath First Search(BFS) 알고리즘에 대해 설명하겠습니다.
1. Depth First Search(DFS)
Depth First Search(DFS)는 깊이 탐색 알고리즘입니다.
특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 경우, 다시 돌아가 다른 경로로 탐색하는 알고리즘입니다.
DFS는 "" 스텍 구조 "" 를 이용하며 구체적인 동작 과정은 아래와 같습니다.
- 탐색 시작 노드를 스텍에 삽입하고 방문 처리를 합니다.
- 스텍의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스텍에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스텍에서 최상단 노드를 꺼냅니다.
- [2]번 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리합니다.
[Example]
시작 노드가 1인 경우,
[Step 1]. $\{\color{red}{1}\}$
[Step 2]. $\{1, \color{ red }{2}\}$
[Step 3]. $\{1, 2, \color{ red }{7}\}$
[Step 4]. $\{1, 2, 7, \color{ red }{6}\}$
[Step 5.] $\{1, 2, 7\}$ (방문하지 않은 인접 노드가 없기 때문에 6번 노드를 꺼냅니다.)
[Step 6]. $\{1, 2, 7, \color{red}{8}\}$
[Step 7]. $\{1, 2, 7\}$
[Step 8]. $\{1, 2\}$
[Step 9]. $\{1\}$
[Step 10]. $\{1, \color{ red }{3}\}$
[Step 11]. $\{1, 3, \color{ red }{4}\}$
[Step 12]. $\{1, 3, 4, \color{ red }{5}\}$
[Step 13]. $\{1, 3, 4\}$
[Step 14]. $\{1, 3\}$ [Step 15]. $\{1\}$
[Step 16]. $\{\}$
최종적으로 $\{ 1, 2, 7, 6, 8, 3, 4, 5 \}$ 순으로 노드를 방문합니다.
DFS는 ""스텍 자료구조""에 기초한다는 점에서 파이썬(python)으로 구현이 간단합니다.
def DFS(graph, v, visited):
visited[v] = True
print(v, end =' ')
for i in graph[v]:
if not visited[i]:
DFS(graph, i, visited)
[Example code]
graphs = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
DFS(graphs, 1, visited)
2. Breath First Search(BFS)
Breath First Search(BFS)는 너비 우선 탐색 알고리즘입니다.
BFS는 가까운 노드부터 탐색하는 알고리즘으로 """ 큐 자료구조 """를 이용합니다.
큐 자료구조를 이용할 경우,
인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되며, 가까운 노드부터 탐색을 진행하게 됩니다.
동작 과정은 아래와 같습니다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
- [2]번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.
[Example]
시작 노드가 1인 경우,
[Step 1]. $\{\color{red}{1}\}$
[Step 2]. $\{1, \color{ red }{2}\}$
[Step 3]. $\{1, 2, \color{ red }{3}\}$
[Step 4]. $\{1, 2, 3, \color{ red }{8}\}$
[Step 5.] $\{2, 3, 8\}$
[Step 6]. $\{2, 3, 8, \color{red}{7}\}$
[Step 7]. $\{3, 8, 7\}$
[Step 8]. $\{3, 8, 7, \color{red}{4}\}$
[Step 9]. $\{3, 8, 7, 4, \color{red}{5}\}$
[Step 10]. $\{8, 7, 4, 5\}$
[Step 11]. $\{7, 4, 5\}$
[Step 12]. $\{7, 4, 5,\color{red}{6}\}$
[Step 13]. $\{4, 5,6\}$
[Step 14]. $\{5,6\}$
[Step 16]. $\{6\}$
[Step 16]. $\{\}$
최종적으로 $\{1,2,3,8,7,4,5,6\}$ 순으로 노드를 방문합니다.
BFS는 ""큐 자료구조""에 기초한다는 점에서 collections 모듈의 dqueue 자료구로를 활용하여 파이썬(python)으로 구현합니다.
from collections import deque
def BFS(graphs, 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[Example code]
graphs = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
BFS(graphs, 1, visited)3. Example
마지막으로 DFS와 BFS 알고리즘을 응용한 대표적인 두 가지 문제를 살펴보고자 합니다.
3.1 DFS 응용 문제: 음료수 얼려 먹기
$N \times M$ 크기의 얼음 틀이 있습니다.
구멍이 뚫려 있는 부분은 9, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 $4 \times 5$ 얼음 틀 예시에서는 아이스크림이 총 $3$개 생성됩니다.
- 입력 조건
- 첫번째 줄에 얼음 틀의 세로 길이 $N$과 가로 길이 $M$이 주어집니다.
- 두 번째 줄부터 $N+1$번째 줄까지 얼음 틀의 형태가 주어집니다.
- 이때 구멍이 뚫려 있는 부분은 0, 그렇지 않은 부분은 1입니다.
- 출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력합니다.
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
x=0;y=0
def drink_dfs(x,y):
## 주어진 범위를 벗어나는 경우 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
## 현재 노드를 방문하지 않은 경우
if graph[x][y] == 0:
## 해당 노드 방문 처리
graph[x][y] = 1
## 상,하,좌,우의 위치도 모두 재귀적으로 호출
## 현재 위치에서 상,하,좌,우로 탐색해서 0인 곳은 1로 치환 -> 각 위치에서 값이 0이였던 경우, 그 위치에서 상,하,좌,우로 탐색.
drink_dfs(x-1,y)
drink_dfs(x+1,y)
drink_dfs(x,y-1)
drink_dfs(x,y+1)
return True
return False
result = 0
for i in range(n):
for j in range(m):
if drink_dfs(i,j) == True:
print(i,j)
result += 1
print(result)3.2 BFS 응용 문제: 미로 탐색
[문제]
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
[입력]
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력]
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
[코드]
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
from collections import deque
def miro_dfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
### 현재 위치에서 네 방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
## 미로 공간을 벗어나는 경우는 무시
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
## 벽인 경우도 무시
if graph[nx][ny] == 0:
continue
## 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1]
print(miro_dfs(0,0))
그림과 같이 새롭게 방문하는 노드에 대해 1씩 더해주는 코드로
마지막 위치에서는 최단 경로의 수가 찍히게 됩니다.
[주 참고교재]: 이것이 취업을 위한 코딩 테스트다 with 파이썬
'Coding Study' 카테고리의 다른 글
| [##프로그래머스 & 백준 coding study ## : 2024.06] (1) | 2024.06.03 |
|---|---|
| [## 프로그래머스 & 백준 coding study ##: 2024.05] (1) | 2024.05.31 |
| [## 프로그래머스 coding study ##: 2024.04] (0) | 2024.04.01 |
| [## 프로그래머스 coding study ##: 2024.03] (0) | 2024.03.13 |
| [## 프로그래머스 coding study ##: 2024.02] (2) | 2024.02.19 |
