유트브 동빈나님의 개념을 활용하여 작성했습니다. 모든 출처는 유트브 동빈나님에서 가져온 것입니다.
🎀기본개념
그래프 : 정점(Node)와 간선(Edge)로 이루어져 있는 자료구조
이런 그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있습니다.
노드를 하나씩 방문하여 모든 노드를 탐색하는 것을 목표로 합니다.
🎀🎀 깊이우선탐색 DFS
- 시작 노드를 기준으로 하여 가장 깊은 노드까지 방문 한 후 다음 노드를 탐색하는 것
DFS 이해하기
방법
[조건]
시작 노드 1
번호가 낮은 인접 노드부터 방문
stack = []
[방법]
- 시작노드를 기준으로 하여 방문한 노드를 stack에 쌓는다.
- 방문하지 않은 노드 중에서 낮은 인접 노드부터 방문하여 stack에 쌓는다.
-
노드 1의 인접노드 : 2, 3
stack => [1 2,3] -
노드 2의 인접노드 : 1, 7
stack => [1,2,3,7] -
노드 7의 인접노드 : 6, 8
stack => [1,2,3,7,6,8] -
노드 6의 인접노드 : 7, 8
stack => [1,2,3,7,6,8] -
노드 8의 인접노드 : 1, 7
stack => [1,2,3,7,6,8] -
노드 3의 인접노드 : 1, 4, 5
stack => [1,2,3,7,6,8,4,5] -
노드 4의 인접노드 : 3, 5
stack => [1,2,3,7,6,8,4,5] -
노드 5의 인접노드 : 3, 4
stack => [1,2,3,7,6,8,4,5]
활용도
- 모든 노드를 방문하고자 할 때 방법 사용
- DFS 가 BFS보다 코드 간결
- BFS보다는 속도가 느림
- Stack | 재귀함수로 구현
🎀🎀 너비우선탐색 BFS
- 시작 노드를 기준으로 하여 인접한 노드를 먼저 탐색하는 방법
- 시작 노드로부터 가장 가까운 노드를 먼저 방문하고, 가장 멀리 떨어져 있는 노드를 나중에 방문하게 된다.
BFS 이해하기
방법
[조건]
Queue 사용(deque)
시작 노드 1
번호가 낮은 인접 노드부터 방문
result = [][방법]
1. 시작 노드 1을 큐에 넣는다.
queue => [1]
-
queue 에서 노드 1을 꺼낸 후 방문하지 않은 인접한 노드 2,3,8을 queue에 넣는다.
queue => [2,3,8]
result => [1] -
queue 에서 노드 2를 꺼낸 후 방문하지 않은 7을 queue에 넣는다.
1은 이미 방문처리가 되어 있기 때문에 PASS
queue => [3,8,7]
result => [1,2] -
queue 에서 노드 3을 꺼낸 뒤 방문하지 않은 4,5를 queue에 넣는다.
queue => [8,7,4,5]
result => [1,2,3] -
queue에서 노드 8을 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다.
1,7 모두 방문되어 있기 때문에 PASS
queue => [7,4,5]
result => [1,2,3,8] -
queue에서 노드 7을 꺼낸 뒤 방문하지 않은 6을 queue에 넣는다.
2,8은 모두 방문되어 있기 때문에 PASS
queue => [4,5,6]
result => [1,2,3,8,7] -
queue에서 노드 4를 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다.
3,5는 모두 방문했기 때문에 PASS
queue => [5,6]
result => [1,2,3,8,7,4] -
queue에서 노드 5를 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다.
3,4는 모두 방문했기 때문에 PASS
queue => [6]
result => [1,2,3,8,7,4,5] -
queue에서 노드 6을 꺼낸 뒤 방문하지 않은 노드를 queue에 넣는다.
7,8은 모두 방문했기 때문에 PASS
queue => []
result => [1,2,3,8,7,4,5,6]
활용도
- 최단 경로를 찾고 싶을 때 사용
- DFS보다 구현이 어려움
- Queue를 사용하여 구현
🎀🎀 DFS와 BFS의 정리
시간복잡도
- 두 방식 모두 모든 노드를 탐색했기 때문에 시간복잡도는 동일합니다.
- N: 노드, E: 간선일 경우
- 인접리스트 : O(N+E)
활용한 문제
- 경로의 특징을 저장해야하는 문제
ex ) 각 정점에 숫자가 있고 a~b까지 가는 경로를 구하는데 경로에 같은 수가 있으면 안된다는 문제등, 각각의 경로마다 특징을 저장해둬야 하는 경우 DFS를 사용. (BFS는 경로의 특징을 가지지 X) - 최단거리를 구하는 문제
미로찾기 등 최단거리를 구해야하는 경우, BFS가 유리 - 검색 대상의 그래프가 크면 DFS사용
- 검색대상의 규모가 크지 않고, 검색 시작 점으로부터 원하는 대상이 멀지 않다면 BFS사용
DFS Python코드
dfs DFS(g, v, visited):
visited[v] = True
print(v, end =' ')
for i in g[v]:
if not visited[i]:
dfs(g, i, visited)
--------------------------------
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
dfs(g, 1, visited)
g의 1번 노드를 비워둔 이유?
-> 시작 노드는 대부분 1부터 시작하기 때문에 비워둔 것
visited에서 왜 9를 한 것인지? 8하면 되는거 아닌가?
-> 첫번째 노드를 비워뒀기 때문에 해당 노드 제외하고 false를 처리해야하기 때문.
그래야 인덱스 1~9번까지 false로 들어가게 된다.
- dfs(g, 1, visited) : 1번 노드부터 시작하겠다 의미
- visited[v] : True : 방문한 노드는 True로 설정
방문한 노드는 출력- for i in g[v] :그래프 도는 동안
- if not visited[i] dfs(g, i, visited) : 방문하지 않은 노드가 있다면, 해당 노드를 탐색
BFS Python코드
from collections import deque
def bfs(g, start, visited):
queue = deque([start])
visited[start] =True
while queue:
v = quque.popleft()
print(v, end =' ')
for i in g[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
----------
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
bfs(g,1,visited)
- queue = deque([start]) : 기준이 되는 노드 queue에 삽입
- visited[start] = True : 해당 노드 방문처리
- while queue : queue 가 빌 때까지
- v = queue.popleft() : 노드 출력
- for i in g[v]
if not visited[i]
queue.append(i)
visited[i] = True
: 인접한 노드들 중 방문하지 않은 노드들을 큐에 삽입 후 방문 처리 하기
