DFS/BFS with 파이썬
1. 꼭 필요한 자료구조 기초
- 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
스택
스택은 흔히 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓는다. 그리고 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 한다. 이러한 구조를 선입후출구조 또는 후입선출구조라고 한다.
stack =[]
for i in range(5):
stack.append(i)
print(stack) # [0, 1, 2, 3, 4]
stack.pop()
print(stack) # [0, 1, 2, 3]
print(stack[::-1]) # [3, 2, 1, 0]
파이썬에서는 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append와 pop 함수를 이용하면 스택 자료구조와 동일하게 동작한다. append는 리스트 맨 뒤에 데이터를 삽입하고 pop은 리스트 맨 뒤에서 데이터를 꺼낸다.
큐
큐는 대기 줄에 비유할 수 있다. 흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람일수록 나중에 들어가기 때문에 흔히 ‘공정한 자료구조’라고 비유된다. 이러한 구조를 선입선출구조라고 한다.
from collections import deque
q = deque()
for i in range(5):
q.append(i)
print(q) # deque([0, 1, 2, 3, 4])
q.popleft()
print(q) # deque([1, 2, 3, 4])
q.reverse()
print(q) # deque([4, 3, 2, 1])
print(list(q)) # [4, 3, 2, 1]
파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 또한 deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 함수를 사용하도록 하자.
재귀 함수
DFS와 BFS를 구현하려면 재귀 함수도 이해하고 있어야 한다. 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 재귀 함수에서 종료 조건을 명시하지 않을 경우 무한대로 제귀 호출을 진행하다가 RecursionError : maximum recursion depth exceeded while pickling an object 와 같이 재귀의 최대 깊이를 초과했다는 내용이 출력된다. 따라서 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 반드시 명시해야 한다.
def recursive_fuc(i):
if i == 4:
return
print(f'{i}번째 함수에서 {i+1}번째 재귀 함수를 호출')
recursive_fuc(i+1)
print(f'{i}번째 재귀 함수를 종료한다')
recursive_fuc(1)
# 출력
1번째 함수에서 2번째 재귀 함수를 호출
2번째 함수에서 3번째 재귀 함수를 호출
3번째 함수에서 4번째 재귀 함수를 호출
3번째 재귀 함수를 종료한다
2번째 재귀 함수를 종료한다
1번째 재귀 함수를 종료한다
컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조 를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다. 물론 재귀 함수를 사용하지 않고 반복문으로도 구현할 수 있다. 하지만 재귀 함수를 사용하면 더욱 간결한 형태로 구현할 수 있다.
2. DFS
DFS는 Depth-First Search, 깊이 우선 탐색이라고 하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 코딩 테스트에서는 이 두 방식 모두 필요하니 알아두자.
- 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
노드가 3개 있는 완전 이진 트리에서 0, 1, 2 가 순서대로 들어 있다고 하고 0과 1은 간선 7로 이어져있고 0과 2는 간선 5로 이어져있다고 가정하자. 먼저 인접 행렬 방식으로 구현해보자.
| 구분 | 0 | 1 | 2 |
| 0 | 0 | 7 | 5 |
| 1 | 7 | 0 | 무한 |
| 2 | 5 | 무한 | 0 |
# 연결 되어 있지 않는 노드끼리는 무한의 비용이라고 작성하자
INF = 999999 # 무한의 비용 선언
graph = [
[0,7,5] # 자기 자신끼리는 0 / 0과 1은 간선 7로 연결/ 0과 2는 간선 5로 연결
[7,0,INF] # 1과 0은 간선 7로 연결 / 자기 자신끼리는 0 / 1과 2은 연결되지 않음
[5,INF,0] # 2와 0은 간선 5로 연결 / 2와 1은 연결되지 않음 / 자기 자신끼리는 0
]
이제 인접 리스트 방식으로 구현해보자.
graph = [[] for _ in range(3)] # 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)
두 방식의 차이
메모리 측면에서 보자면 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많은수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.
예를 들어 노드1과 노드 7이 연결되어 있는지 확인해보자. 인접 행렬 방식에서는 graph[1][7]만 확인하면 된다. 반면에 인접 리스트 방식에서는 노드1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다. 그러므로 특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간 낭비가 적다.
시간 복잡도
- 인접 리스트로 표현할 경우 : O(V+E)
- 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하기 때문
- 인접 행렬로 표현할 경우 : O(V^2)
- for loop를 V만큼 돌기 때문에 O(V) 시간이 필요한데 모든 정점을 방문할 때마다 dfs를 호출하므로 V * O(V) = O(V^2)
- for loop를 V만큼 돌기 때문에 O(V) 시간이 필요한데 모든 정점을 방문할 때마다 dfs를 호출하므로 V * O(V) = O(V^2)
DFS 동작 과정
본격적으로 DFS를 살펴보자. DFS는 깊이 우선 탐색 알고리즘이라고 했다. 이 알고리즘은 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘이다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
cf) 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러개 있으면 번호가 낮은 순서부터 처리한다. DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 종종 있기에 관행적으로 번호가 낮은 순서부터 처리하도록 구현하는 편이다.
def dfs(graph,start,visited):
print(start, end=" ") # 방문했다고 출력
visited[start] = True # 현재 위치 방문 표시
for i in graph[start]: # 다음 위치
if visited[i] == False: # 다음 위치가 가본적 없는 곳
dfs(graph,i,visited) # 다음 위치를 기준으로 다시 dfs
# 편의상 그래프는 1~ 8까지 있다고 가정
# 순회해야하므로 인접 리스트 방식이 수월
graph =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
# 노드 1부터 8까지이므로 0은 무시하고 *9해야함
visited=[False]*9
dfs(graph,1,visited)
# 1 2 7 6 8 3 4 5
깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. DFS는 스택을 이용하는 알고리즘이기에 재귀를 사용하면 매우 간결하게 구현할 수 있다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N인 경우 O(N)의 시간이 소요된다.
3. BFS
BFS(Breath First Search) 알고리즘은 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 동작 방식은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복
from collections import deque
def bfs(graph,start,visited):
queue = deque([start])
visited[start] = True
while queue: # 큐 안에 원소가 있다면
ans = queue.popleft()
print(ans,end = " ")
for i in graph[ans]: # 꺼낸 원소 주변에 있는 것들 대상으로
if visited[i] == False: # 대상이 방문한적이 없다면
queue.append(i)
visited[i]=True
# 편의상 그래프는 1~ 8까지 있다고 가정
# 순회해야하므로 인접 리스트 방식이 수월
graph =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현
# 노드 1부터 8까지이므로 0은 무시하고 *9해야함
visited=[False]*9
bfs(graph,1,visited)
# 1 2 3 8 7 4 5 6
- 인접 리스트로 표현할 경우 : O(V+E)
- 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 검사하기 때문
- 인접 행렬로 표현할 경우 : O(V^2)
- for loop를 V만큼 돌기 때문에 O(V) 시간이 필요한데 모든 정점을 방문할 때마다 bfs를 호출하므로 V * O(V) = O(V^2)
4. 정리
| 구분 | DFS | BFS |
|---|---|---|
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
BFS와 DFS를 앞서 그래프 그림을 이용해 이해했는데 1차원 배열이나 2차원 배열 또한 그래프 형태로 생각하면 수월하게 풀 수 있다. 그러므로 코딩 테스트에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민해보자.
BFS와 DFS 어느 것을 선택할까?
사실 코드레벨에서 본다면 DFS가 BFS보다 훨씬 간단하다. 따라서 DFS와 BFS로 모두 풀 수 있는 경우에는 DFS를 사용하는 것이 편할 수 있다.
예시로 목적지가 정해져 있는 미로에서 최소 이동 칸 수를 구하는 문제를 보면 갈림길에서 어디로 이동해야 할지 선택해야 한다. 이런 경우에는 BFS를 통해 해당 좌표마다 그래프에 이동 칸수를 저장해두면 된다. 이처럼 해당 좌표를 기준으로 모든 경로에 대해 고려가 필요하다면 BFS를 사용하는 것이 좋은 선택이다.
최종 목적지가 정해져 있지 않은 단순히 어느 조건에 따라 탐색하고 탐색한 위치를 방문처리하고 탐색을 종료하는 경우라면 DFS를 사용하는 것이 좋은 선택이다.
참고로 코딩 테스트에서 재귀 함수로 DFS를 구현할 경우, 컴퓨터 시스템 동작 특성상 실제 프로그램의 수행 시간이 느려질 수 있어 조금 더 빠르게 구현하고 싶다면 BFS를 사용해야 한다.
5. 실전문제
문제 : 음료수 얼려 먹기
N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
입력조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다 (1<=N,M<=1000)
- 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍 뚫린 부분은 0 아닌 부분은 1
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수 출력
입력 예시
4 5
00110
00011
11111
00000
출력 예시
3
풀이
# DFS 풀이
n, m = map(int, input().split())
graph = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 그래프 작성
for i in range(n):
graph.append(list(map(int, input())))
def dfs(graph, x, y):
graph[x][y] = 1
for i in range(4):
px = x + dx[i]
py = y + dy[i]
# 범위 내
if 0 <= px and px < n and 0 <= py and py < m:
# 미방문시
if graph[px][py] == 0:
dfs(graph, px, py)
cnt = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
cnt += 1
dfs(graph, i, j)
print(cnt)
# BFS 풀이
from collections import deque
n, m = map(int, input().split())
graph = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
ans =0
for i in range(n):
graph.append(list(map(int, input())))
def bfs(graph,x,y):
graph[x][y]=1 # 방문 처리
q = deque()
q.append((x,y))
while q:
x,y = q.popleft()
for i in range(4):
px = x + dx[i]
py = y + dy[i]
if 0<=px and px<n and 0<=py and py<m:
if graph[px][py] == 0:
q.append((px,py))
graph[px][py]=1
for x in range(n):
for y in range(m):
if graph[x][y] == 0:
bfs(graph,x,y)
ans+=1
print(ans)
이 문제는 DFS, BFS로 해결할 수 있다. 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링할 수 있다.
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
- 1~2 과정을 모든 노드에 대해서 반복한다.
cf) 그래프 작성
그래프를 입력받을 때 공백으로 구분되어 있지 않아 당황했다. 공백으로 구분되어 있다면 list(map(int,input().split()))을 append했으면 됬는데 이 경우에는 좀 달랐다. 여기서는 split()을 붙이면 안된다. spilt을 붙이게 될 경우 00110을 하나의 문자로 인식하기 때문이다. split을 붙이지 않으면 00110을 각각의 개별 문자로 인식하면서 하나씩 처리된다.
문제 : 미로 탈출
캐릭터가 N * M크기의 직사각형 미로에 갇혀 있다. 미로에는 괴물이 있어 피해서 탈출해야 한다. 캐릭터의 위치는 (1,1)이고 출구의 위치는 (N,M)에 존재한다. 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시되어 있다. 탈출하기 위해서 움직여야하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력 조건
첫째 줄에 두 정수 N,M이 주어진다. 다음 N개의 줄에는 각각 M개의 정수로 미로 정보가 주어진다. 각각의 수들은 공백없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력 조건
첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력 예시
5 6
101010
111111
000001
111111
111111
출력예시
10
풀이
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 그래프 만들기
for _ in range(n):
graph.append(list(map(int, input().rstrip())))
def bfs(x, y):
q = deque([(x,y)])
while q:
x, y = q.popleft()
for i in range(4):
px = x + dx[i]
py = y + dy[i]
# 범위 내
if 0 <= px and px < n and 0 <= py and py < m:
# 빈칸
if graph[px][py] == 1:
graph[px][py] = graph[x][y] + 1
q.append((px, py))
# 주어지는 시작점은 1,1이지만 0.0으로 가정하고 인덱스와 맞추는게 편함
bfs(0, 0)
print(graph[n - 1][m - 1])
이 문제는 BFS를 이용했을 때 매우 효과적으로 해결할 수 있다. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.
Cf) 지도 만들때 혼동되었던 점
game_map = []
game_map.append(list(map(int,input())))
print(game_map)
#결과는 [[0, 0, 1, 1, 0, 0]]
# 문자열을 입력받고 그 문자열 각각의 원소 하나씩 map으로 인해 int로 변환
# 후에 리스트로 다시 변환
import sys
graph = []
graph.append(list(map(int,sys.stdin.readline().rstrip().split())))
print(graph)
# 결과는 [[1100]]
# 이유는 split()때문이다. 공백이 없이 입력되었으므로 split()으로 인해 001100을 하나로 인식
# map에 001100이 들어가고 int변환시 앞에 00이 사라짐.
# 똑같이 사용하려면 split을 지우면 된다.
# rstrip()은 오른쪽 개행문자를 지우기 위해 반드시 필요하다.
0055
0006
같은 문자열을 int형 변환하면 앞의 0들은 삭제된다.
