야금야금 공부
[이코테] 5장 DFS/BFS 본문
DFS/BFS
그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
- 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 코딩 테스트에서 매우 자주 등장하는 유형
- 필요 자료구조 : 스택, 큐, 재귀함수
DFS (깊이 우선 탐색)
깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 혹은 재귀 함수를 이용
[동작 과정]
1. 탐색 시작 노드를 스택에 넣고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 1개라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.
3. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
4. 더 이상 2번 과정을 수행할 수 없을 때까지 반복
(방문 기준 : 번호가 낮은 순서)
시작 노드 : 1
# DFS 메서드 정의
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차원 리스트)
graph = [
[], # 시작 노드 : 1
[2, 3, 8], # 1번 노드의 인점 노드
[1, 7], # 2번 노드의 인접 노드
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9 # 처음엔 모두 False로 초기화
# 인덱스 0을 사용하지 않기 위해 하나더 큰 공간 생성
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
BFS(너비 우선 탐색)
가까운 노드부터 탐색하는 알고리즘
- 큐 사용
[동작 과정]
1. 탐색 시작 노드를 큐에 넣고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
(방문 기준 : 번호가 낮은 인접 노드부터)
시작 노드 : 1
- 거리가 가까운 순으로 방문 => 최단 거리 문제에 적용 가능
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 사용
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
# 각 노드가 연결된 정보(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
< DFS와 BFS 차이 >
DFS | BFS | |
동작 원리 | 스택 | 큐 |
구현 방법 | 재귀 함수 이용 | 큐 이용(deque) |
'알고리즘' 카테고리의 다른 글
[이코테] 8장 다이나믹 프로그래밍(동적 계획법) (0) | 2023.05.01 |
---|---|
[이코테] 6장 정렬 (0) | 2023.01.31 |
[Python] 백준 11047번 동전 0 (0) | 2022.12.02 |
[이코테] 3장 그리디 (0) | 2022.12.02 |
[Python] 백준 14888번 연산자 끼워넣기 (0) | 2022.12.01 |