🎠탐색 알고리즘 중 DFS와 BFS를 공부하고 문제를 풀어보자
1. DFS(깊이 우선 탐색, depth-first serach)
- 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행한다.
| 기능 | 특징 | 시작 복잡도(노드 수 : V, 에지 수: E) |
| 그래프 완전 탐색 | 재귀함수로 구현 스택 자료구조 이용 |
O(V+E) |
1-1. 특징
- 스택 오버플로(stack overflow)에 유의
- 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등
1-2. 핵심이론
- 한번 방문한 노드를 다시 방문하면 안됨 -> 노드 방문 여부를 체크할 리스트 필요
- 후입선출
01
1-3. 예제
import sys
n, m = map(int, sys.stdin.readline().split())
# 특정 노드 방문하고 연결된 모든 노드들 방문
def dfs(x, y) :
# 주어진 범위를 벗어나면 종료
if x <= -1 or x >= n or y <= -1 of y >= m :
return false
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0 :
# 해당 노드 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우 모두 재귀 호출
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n) :
graph.append(list(map(int, sys.stdin.readline().split())))
# 모든 노드에 대해 음료수 채우기
result = 0
for i in range(n) :
for j in range(m) :
# 현재 위치에서 DFS 수행
if dfs(i, j) == True :
result += 1
# 정답 출력
print(result)
2. BFS(너비 우선 탐색, Breadth-first search)
- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색한다.
| 기능 | 특징 | 시간 복잡도(노드 수 : V, 에지 수 : E) |
| 그래프 완전 탐색 | FIFO 탐색 Queue 자료구조 이용 |
O(V+E) |
2-1. 특징
- 선입선출 -> 큐 사용
- 최단 경로 보장
2-2. 핵심 이론
- 한번 방문한 노드를 다시 방문하면 안됨 -> 노드 방문 여부를 체크할 리스트 필요
01
2-3. 예제
from collections import deque
import sys
# 이동할 네 방향 정의(상, 하, 좌, 우)
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# BFS 코드 구현
def BFS(x, y) :
# 큐를 사용하기 위해 deque 라이브러리 사용
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 nx >= n or ny < 0 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]
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n) :
graph.append(list(mat(int, sys.stdin.readline().rstrip())))
print(bfs(0, 0))🌸 탐색 알고리즘 문제는 그래도 좀 풀 수 있다고 생각했는데 DFS랑 BFS를 섞은 이상한 방식으로 풀고 있었다... 개념 정리랑 알고리즘 흐름을 아는 게 중요한 것 같다. 두 방식이 헷갈렸는데 depth는 한쪽 길을 정해서 끝까지 가보는 거고 breadth는 한 노드에서 갈 수 있는 모든 노드를 찍먹 하는 거로 외웠다.
🌸코드를 짤 때 중요한 건 DFS는 graph에 0과 1(or True와 False)을 이용해서 방문 처리를 하는 거고 BFS는 graph에서 이동한 거리 수를 구하는 것이다. 이 두 개 차이점을 기억해야겠다.
🌸어떤 문제에서 어떤 방법을 써야하는지 잘 모르겠다. 최단 거리를 구할 땐 BFS를 쓰는 거 같은데 다른 문제 방식에서는 뭘 써야 하는 걸까
출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬(한빛미디어), 알고리즘 코딩 테스트 파이썬 편(이지스 퍼블리싱)