[python] DFS/BFS 정리

---

* BFS (Breath-Frist Search)

---

- 너비 우선 탐색

- 큐(deque) 사용 

- 현재 위치에서 가장 가까운 노드들을 모두 방문 

- 현재 위치 pop, 방문할 곳 append, 방문한 곳 check

 

☞ 미로 탐색 중 최단 거리를 찾는 문제

☞ 임의의 경로를 찾는 문제 

 

BFS 장/단점

- 장점: 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장함 

- 단점: 경로가 매우 길 경우 탐색가지가 급격히 증가하여 많은 기억 공간이 필요함

           해가 존재하지 않는다면 유한 그래프인 경우, 그래프 탐색 후 실패로 끝남

           다만 무한 그래프인 경우에는 해를 찾지도 끝내지도 못한다.   

            

 

ex) 우리나라에서 직통도로로 연결된 지역 중, 서울과 경기도 사이에 존재하는 경로를 찾고싶을 때 
     깊이 우선 탐색의 경우(DFS) - 전국의 모든 도로를 다 살펴봐야할 수도 있다.
     너비 우선 탐색의 경우(BFS) - 서울과 인접한 도로먼저 탐색

from collections import deque 
visited = [False] * 10 

def bfs(v): 
    q = deque([v]) 
    visited[v] = True 
    
    while q: # 큐가 비지 않는 동안 
    	a = q.popleft() 
        print(a,end=' ') 
        w = sorted(graph[a]) # 번호가 작은 곳부터 순서대로 방문하기 위해 정렬 
        for i in w: 
        	if not visited[i]: 
            	q.append(i) # 방문할 곳 append 
                visited[i] = True # 방문한 곳 check

 

---

* DFS(Depth-First Search)

---

- 깊이 우선 탐색

- 스택(stack) 또는 재귀(recursion) 사용 

- 현재 위치에서 연결된 브랜치를 모두 방문 후 다음 브랜치로 넘어가는 방법

- 미로 탐색시 한 방향으로 갈 수 있을 때까지 가다가 더이상 갈 곳이 없다면

  다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 탐색을 진행하는 방법

  (더이상 들어갈 곳이 없을때까지 깊게 탐색)

 

☞ 모든 노드를 방문하고자 할 때 이 방법을 선택함

☞ 미로 탐색시 이동할 때마다 가중치가 붙거나 이동 과정에서 제약이 있는 경우 

 

DFS 장/단점

- 장점: 찾고자 하는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 동작함

- 단점: 해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색 

           효율성을 높이기 위해서는 지정한 깊이까지만 탐색하고 해를 발견하지 못할 경우 빠져나와

           다른 경로를 탐색하도록 구현 

 

def dfs(v): 
    if visited[v]: 
        return 
    visited[v] = True 
    print(v,end = ' ') 
    w = sorted(graph[v])
    for i in w: 
    	if not visited[i]: 
        	dfs(i)

 

 

[DFS vs BFS 탐색 차이]

 

출처 :

https://covenant.tistory.com/132

https://na0dev.tistory.com/32