BFS & DFS 문제 구분

► BFS (Breadth-First Search)

- 너비 우선 탐색

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

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

 

☞  미로탐색 중 최단 거리를 찾는 문제, 임의의 경로를 찾는 문제에서 사용

 

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)

- 깊이 우선 탐색

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

- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법

 

☞  모든 노드를 방문하고자 할 때 이 방법을 선택. 또는 미로탐색 진행 시 이동할 때 마다 가중치가 붙거나 이동 과정에서 제약이 있을 경우

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