.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
DFS, BFS 알고리즘
•
DFS : 깊이 우선 탐색
•
BFS : 너비 우선 탐색
탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
•
스택(Stack) 자료구조를 자주 사용
DFS(Depth-First Search)
•
깊이 우선 탐색
•
그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
•
스택 자료구조(혹은 재귀 함수)를 사용
동작과정
1.
시작 노드를 방문 처리
2.
현재 노드와 연결된 다른 노드 중 방문하지 않은 노드를 방문
3.
방문하지 않은 노드가 없다면 종료
4.
2~3번을 반복
실제 함수 동작
def dfs(graph, v, visited): # graph: 그래프, v: 시작 노드, visited: 방문 여부
visited[v] = True # 현재 노드 방문 처리
print(v, end=' ') # 방문한 노드 출력
for i in graph[v]: # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 graph[a, b]
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],
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
#우리가 1번 인덱스부터 사용하기 때문에 하나 더 큰 크기로 1차원 리스트 초기화
visited = [False] *9
#정의된 dfs 함수 호출
dfs(graph, 1, visited)
Python
복사
구현 순서
1.
그래프 2차원 배열 제작
2.
방문 노드 배열 제작
3.
dfs 재귀 함수 제작
a.
현재 노드 방문 여부 True로 변환
b.
그래프 배열에서 다른 노드 값이 False인 노드가 있는지 검증
c.
값이 False라면 재귀 수행
d.
True라면 PASS
BFS(Breadth-First Search)
•
너비 우선 탐색
•
가까운 노드부터 우선적으로 탐색하는 알고리즘
•
큐 자료구조 사용
동작과정
1.
시작점을 큐에 넣는다.
2.
큐에서 하나를 꺼내서 방문한다.
3.
방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 넣는다.
4.
큐가 빌 때까지 2~3번 반복
실제 함수 동작 : deque
from collections import deque
#큐 구현을 위해 deque 라이브러리 사용
#BFS 메서드 정의
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]
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
#정의된 BFS 함수 호출
bfs(graph, 1, visited)
Python
복사
•
큐 동작 순서
1.
먼저 1번(2,3,8) 노드 방문
•
1번 노드 True 처리
•
큐에 2, 3, 8 삽입 (2, 3, 8)
2.
2번(1,7) 노드 방문
•
2번 노드 True 처리
•
큐에 2제거, 1번은 다녀왔으니 7만 삽입 (3, 8, 7)
3.
3번(1,4,5) 노드 방문
•
3번 노드 True 처리
•
큐에 3제거, 1번은 다녀왔으니 4,5만 삽입 (8, 7, 4, 5)
4.
8번(1,7) 노드 방문
•
8번 노드 True 처리
•
큐에서 8만 제거(1,7은 다녀왔으므로) (7,4,5)
5.
7번(2,6,8) 노드 방문
•
7번 노드 True 처리
•
큐에 7제거, 2,8은 다녀왔으니 6만 삽입 (4,5,6)
6.
나머지 노드 방문 - 큐에 모든 False 노드가 들어가있으므로
•
순차적으로 큐에서 제거
구현 순서
1.
그래프 2차원 배열 제작
2.
방문 노드 배열 제작
3.
bfs 함수 제작 (deque 사용)
a.
현재 노드 방문 여부 True로 변환
b.
현재 노드는 queue에서 제거, 해당 노드에서 방문하지 않은 노드는 queue에 삽입
c.
a,b 반복
예시
•
그래프의 모든 정점을 방문하는 것이 주요한 문제
◦
모든 정점을 방문하는 것이 중요한 문제의 경우
▪
DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관X
•
경로의 특징을 저장해둬야 하는 문제 = DFS
◦
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등
◦
각 경로마다 특징을 저장해둬야 할 때는 DFS를 사용 (이유 : BFS는 경로의 특징을 가지지 못함)
•
최단거리 구해야 하는 문제 = BFS
◦
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리
깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문
•
기타
◦
검색 대상 그래프가 정말 크다면 DFS를 고려
◦
재귀 사용시 DFS
◦
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
