Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
DFS와 BFS
자료구조 기초
- 탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정
- 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
1. 스택
- 선입후출(FIFO) 방식의 자료 구조
-
- 예시: 배열 [ ]
- 5 삽입 [5] ➝ 8 삽입 [5, 8] ➝ 1 삽입 [5, 8, 1] ➝ 삭제: [5, 8] ➝ 삭제 [5]
- 파이썬에서 스택 사용: 별도의 라이브러리를 사용하지 않고 기본 리스트 사용
stack = [] stack.append(3) # 배열에 3 삽입 stack.pop() # 가장 나중에 삽입된 원소 삭제
2. 큐
- 나중에 들어온 요소가 나중에 나가는
선입선출구조 -
- 예시: 배열 [ ]
- 5 삽입 [5] ➝ 8 삽입 [5, 8] ➝ 1 삽입 [5, 8, 1] ➝ 삭제: [8, 1] ➝ 삭제 [1]
-
파이썬에서의 큐 사용: collections모듈의 deque 자료구조 활용
from collections import deque queue = deque() # 큐 구현을 위해 deque 라이브러리 사용 queue.append(5) # 추가 queue.popleft() # 삭제
재귀함수
- 자기 자신을 다시 호출하는 함수
- 파이썬 인터프리터는 호출 횟수 제한이 있어 무한대로 재귀 호출을 진행할 수 없다. 재귀함수의 종료조건
- 재귀함수를 사용할 때는 종료조건을 꼭 명시해 무한 호출을 방지해야한다.
-
재귀 함수의 수행 = 스택 자료구조 이용: 함수를 계속 호출하면 가장 마지막에 호출된 함수의 수행이 끝나야 그 이전의 함수들이 종료되기 때문 ➝ 스택 자료구조를 활용해야하는 알고리즘들을 재귀함수로 간편하게 구현될 수 있다 (ex. DFS)
- 하지만 재귀함수로 풀리는 문제들은 반복문으로도 풀 수 있다.. 왜 재귀함수를 이용하는 걸까?
- 코드가 간결해진다: 수학의 점화식을 그대로 옮겼기 때문
DFS
- Depth-First Search: 깊이 우선 탐색
- 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
- 특정한 경로를 탐색하다가 특정 상황에서 최대한 깊숙히 들어가 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘
동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리.
- 만약 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 과정 반복
DFS 과정
- 시작 노드 1부터 스택에 삽입 : [1]
- 1과 인접 노드인 2, 3, 8중 가장 작은 2 먼저 방문하고 스택에 넣는다. : [1, 2]
- 2의 인접노드인 7을 방문하고 스택에 넣는다. : [1, 2, 7]
- 7과 인접 노드인 6, 8 중 더 작은 6을 방문하고 스택에 넣는다. : [1, 2, 7, 6]
- 6에서는 더 방문할 노드가 존재하지 않으므로 스택에서 제거한다. : [1, 2, 7]
- 7과 인접한 노드인 8을 방문하고 스택에 넣는다. : [1, 2, 7, 8]
- 8에서 더 방문할 노드가 없으니 스택에서 제거한다. : [1, 2, 7]
- 7, 2에서도 더 방문할 노드가 없으니 스택에서 제거한다. : [1]
- 1의 인접 노드인 3을 방문하고 스택에 넣는다. : [1, 3]
- 3과 인접 노드인 4를 방문하고 스택에 넣는다. : [1, 3, 4]
- 4의 인접 노드인 5를 방문하고 스택에 넣는다. : [1, 3, 4, 5]
- 더 이상 방문할 노드가 없으므로 스택에서 차례대로 제거한다.: 5 ➝ 4 ➝ 3 ➝1순으로 제거
- 방문 순서: 1, 2, 7, 6, 8, 3, 4, 5
코드
def dfs(graph, v, visited):
visited[v] = True
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS
- Breadth First Search = 너비 우선 탐색 알고리즘
- 가까운 노드부터 탐색하는 알고리즘
- 큐 자료구조를 이용하는 것이 정석
- 언접 노드를 반복적으로 큐에 넣도록 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어 가까운 노드부터 탐색을 진행하게 된다.
동작 방식
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 과정 반복
BFS 과정
1) 시작 노드 1을 큐에 삽입하고 방문처리 : [1]
2) 큐에서 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8을 큐에 삽입 : [2, 3, 8]
3) 큐에서 2를 꺼내고 2에 인접하며 방문하지 않은 노드인 7을 큐에 삽입 : [3, 8, 7]
4) 큐에서 3을 꺼내고 3과 인접하며 방문하지 않은 노드인 4, 5를 큐에 삽입 : [8, 7, 4, 5]
5) 큐에서 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시: [7, 4, 5]
6) 큐에서 7을 꺼내고 7과 인접하며 방문하지 않은 노드인 6을 큐에 삽입: [4, 5, 6]
7) 모든 노드를 방문하였으므로 차례대로 노드를 꺼낸다.: 4 ➝ 5 ➝ 6 순으로 제거
- 탐색 순서: 1, 2, 3, 8, 7, 4, 5, 6
코드
from collections import deque
def bfs(graph, 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
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)
정리
- DFS: 스택(재귀함수) 이용
- BFS: 큐 자료구조 이용
