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 리스트 혹은 큐 혹은 뭐 들어있는 거 :
	반복문 
    
#들어있는 놈이 빌 때까지 반복문 실행!