DFS와 BFS

DFS와 BFS

DFS란?

Depth First Search, 깊이 우선 탐색

깊은 부분을 우선적으로 탐색하는 알고리즘 -> 더 깊이, 끝까지 들어가본다

스택 자료구조 ( 또는 재귀함수 ) 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드(맨 위, 먼저 빠지는 놈)에 있는 놈 부근에 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문 처리

3. 방문하지 않은 인접 노드가 없으면 ( 근처에 다 방문했으면 ) 스택에서 최상단 노드 꺼냄

4. 2~3 과정 수행할 수 없을 때까지 반복

DFS 동작 예시

출처 : 유튜브 동빈나 님

- 시작 노드 : 1

- 방문 기준 : 번호가 낮은 인접 노드부터

1번 방문 처리 -> 2번 방문 처리 -> 7번 방문 처리 -> 6번 방문 처리

스택 최상단 노드인 6번 부근에 인접 노드가 없으므로 스택에서 뺀다 -> 7번 인접 노드인 8번 방문 처리

스택 최상단 노드인 8번 부근에 인접 노드가 없으므로 뺀다 -> 최상단 노드 부근에 인접 노드가 있을 때까지 뺀다

-> 최상단 노드가 1번이 되고 인접 노드인 3 방문 -> 4 방문 -> 5 방문

방문 순서 : 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

6번까지 깊게 파고 들어가서 탐색한다 = 깊이 우선 탐색

각 번호마다 인접 노드를 찾는 동일한 메커니즘을 계속 수행해준다 = 재귀 (나중에 코드로 칠 때 이 재귀의 개념 이해 )

코드로 보기

graph = [ [], #인덱스랑 번호 맞추기 위해 앞에 빈 리스트 추가 [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False]*9 #[False,False,False,False,False,False,False,False,False] def dfs(graph,v,visited): #v는 시작 노드 visited[v] = True #현재 노드 방문 체크 print(v,end='') #방문한 순서 적어주는 (출력해주는) 코드. end='' 의미는 줄 띄우는 거 없이 출력한다는 뜻 for i in graph[v]: #방문 노드의 인접 노드를 살펴본다 if not visited[v]: #인접 노드가 False라면 = 인접 노드에 아직 방문하지 않았다면 dfs(graph,i,visited) #이 함수를 재귀적으로 사용해라 = 파고 들어가보자 = 깊이 우선 탐색!

* if not

더보기 if not ABC : 실행구문 #ABC가 false 라면 , 실행구문 해라!

BFS란?

Breadth First Search, 너비 우선 탐색

가까운 노드를 우선 적으로 탐색하는 알고리즘 -> 최단 경로 탐색

큐 자료 구조 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내고(큐 자료 구조에서는 먼저 들어간 놈이 먼저 빠짐) 빠지는 놈 부근에 방문하지 않은 노드가 있으면 그 노드를 모두 큐에 넣고 모두 방문 처리

3. 방문하지 않은 인접 노드가 없으면 ( 근처에 다 방문했으면 ) 큐에서 노드 꺼냄

4. 2~3 과정 수행할 수 없을 때까지 반복

BFS 동작 예시

출처 : 유튜브 동빈나 님

- 시작 노드 : 1

- 방문 기준 : 번호가 낮은 인접 노드부터

1번 방문 처리 후 큐에 삽입 -> 1번 노드 큐에서 빼고 인접 노드인 2, 3, 8번 방문 처리 후 큐에 삽입

2번 큐에서 빼고 2번 인접 노드 중 방문 안한 7번 방문 처리 후 큐에 삽입

3번 큐에서 빼고 인접 노드 중 방문 안한 4, 5번 방문 처리 후 큐에 삽입

큐 밑에서부터 빼면서 방문 안한 인접 노드 있는 번호까지 계속 뺌

7번 인접 노드 중 방문 안한 6번 있으므로 6번 방문 처리 후 큐에 삽입

큐에서 모든 번호가 사라질 때 까지 빼면 동작 종료

탐색 순서 : 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

길이가 1인 노드부터 우선적으로 탐색된다 -> 최단 경로 탐색

코드로 보기

from collections import deque graph = [ [], #인덱스랑 번호 맞추기 위해 앞에 빈 리스트 추가 [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False]*9 #[False,False,False,False,False,False,False,False,False] def bfs(graph,start,visited): queue = deque([start]) #queue라는 이름으로 큐 자료구조를 만들고, start 먼저 넣어줌 visited[start] = True #방문 처리 while queue: #while 리스트: 의 의미 = 리스트가 빌 때까지!!! -> queue가 빌 때까지 반복 v=queue.popleft() #리스트의 왼쪽부터 꺼낸다 = 큐에서 젤 먼저 들어온 놈부터 꺼낸다 print(v,end=' ') #방문 순서 출력 for i in graph[v]: #큐에서 꺼낸 놈의 인접 노드에서 하나씩 보자 if not visited[i]: #하나씩 봐서 만약 아직 방문 안했던 거라면 queue.append(i) #큐에 넣어주고 visited[i]=True #방문처리 해라

*while queue:

더보기 while 리스트 혹은 큐 혹은 뭐 들어있는 거 : 반복문 #들어있는 놈이 빌 때까지 반복문 실행!

from http://newwave.tistory.com/86 by ccl(A) rewrite - 2021-08-04 21:26:13