파이썬의 자료구조 - DFS, BFS

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.

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

출처 https://developer-mac.tistory.com/64
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말함.
말 그대로 깊이 우선이므로 제일 왼쪽에 있는 노드를 끝까지 내려간다음 다음 노드로 이동한다.

특징

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
• 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

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

출처 https://developer-mac.tistory.com/64
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

차이점

• 깊이 우선 탐색의 경우 : 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 : 본인과 가까운 관계부터 탐색

두 방식의 비교

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

DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도 자체는 동일하다.
(DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간의 합)
이를 활용하여 코드로 구현해보겠다.

DFS

def DFS_with_adj_list(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

print(BFS_with_adj_list(graph_list, root_node))

BFS

from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

아래는 DFS, BFS을 활용한 미로탐색 코드이다.

from collections import deque
# 상하좌우 탐색을 위한 리스트 선언 (평면 좌표 느낌으로 세팅해 준 것) x는 좌우, y는 상하만
dx = [0, 1, 0, -1] 
dy = [1, 0, -1, 0]
N, M = map(int, input().split()) 
A = [[0] * M for _ in range(N)] # 2차원 행렬 저장
visited = [[False] * M for _ in range(N)] # 방문 기록을 저장하는 리스트

for i in range(N) :
    numbers = list(input())
    for j in range(M) :
        A[i][j] = int(numbers[j]) # 리스트 기록

def BFS(i, j) :
    queue = deque() # 큐에 첫 노드 삽입
    queue.append((i,j)) 
    visited[i][j] = True # visited 리스트에 해당 노드을 기록 (True : 지나감)
    while queue : # 큐가 빌 때까지 (queue가 있을때 반복)
        now = queue.popleft() # 큐에서 노드 데이터를 가져오기
        for k in range(4) : # 상하좌우 탐색
            x = now[0] + dx[k] 
            y = now[1] + dy[k]
            if x >= 0 and y>=0 and x< N and y<M : # 유효한 좌표 확인
                if A[x][y] != 0 and not visited[x][y] : # 이동할 수 있는데 방문하지 않은 노드
                    visited[x][y] = True # 리스트에 방문 기록
                    A[x][y] = A[now[0]][now[1]]+1 # A 리스트에 depth를 현재 노드의 depth + 1로 업데이트
                    queue.append((x,y)) # 큐에 데이터 삽입

BFS(0,0)
print(A[N-1][M-1])