[python] 너비우선탐색, 깊이우선탐색(bfs, dfs)

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

출처 https://developer-mac.tistory.com/64

 

💡 깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에

해당 분기를 완벽하게 탐색하는 방식을 말합니다.

 

2. 너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

출처 https://developer-mac.tistory.com/64

 

💡 너비 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

​

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

​

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

​

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.

​

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

 

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,

너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

​

4. dfs / bfs 코딩

1) dfs

스택에 쌓고 방문 처리하고 팝 하면서 그 노드에 연결된 노드 스택에 쌓고 방문 처리...

def DFS(graph, root):
    visited=[]
    stack = []
    stack.append(root)
    
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            for i in graph[n]:
                if i not in visited:
                    stack.append(i)
            
    return visited

2) bfs

큐에 넣고 방문 처리하고 팝하면서 그 노드에 연결된 노드들 큐에 넣고 방문 처리...

 

from collections import deque

def BFS(graph, root):
    visited=[]
    q = deque()
    q.append(root)
    
    while q:
        n = q.popleft()
        if n not in visited:
            visited.append(n)
            for i in graph[n]:
                if i not in visited:
                    q.append(i)
            
    return visited