[알고리즘] BFS와 DFS의 개념, 차이점과 구현(Python)

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

---

인접한 노드를 먼저 탐색하는 방식 (매 단계에서 가능한 경우의 수들을 모두 확인하면서 탐색)

* 최대한 넓게 이동하여 더 이상 옆으로 갈 곳이 없을 경우 아래로 이동

 

 

1. Queue를 통해 구현

2. 최단 경로를 찾을 때 주로 사용

 

탐색 경로를 결과로 출력한다고 하면 BFS의 파이썬 구현 코드는 다음과 같다.

* 양방향 큐(deque) 사용

# N×N 2차원 배열

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

# 방문한 노드일 경우 True / 방문하지 않은 노드일 경우 False
visited = [[False for _ in range(N)] for _ in range(N)]


def BFS(r, c):
    q = deque()  # 탐색해야 하는 노드들을 담는 큐
    
    # 탐색을 시작하는 노드 (r, c)
    q.append((r, c))
    visited[r][c] = True
    
    route = []  # 탐색 경로 저장
    route.append((r, c))

    # 큐에 들어가 있는 노드가 없을 때까지(탐색이 완료될 때까지) 반복
    while q:
        # 현재 탐색 중인 노드 (y, x)
        y, x = q.popleft()
        
        for i in range(4):
            # 인접 노드 (ny, nx)
            ny = y + dy[i]
            nx = x + dx[i]
            
            # 조건문을 통해 탐색 가능한 노드인지 확인
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx))  # 인접한 노드를 전부 탐색하기 위해 큐에 다시 append
                route.append((ny, nx))
                
    return route

 

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

---

한 노드에서 시작하여 한 분기(branch)를 완벽하게 탐색한 후 다음 분기로 넘어가는 방식

* 최대한 깊이 내려가서 더 이상 내려갈 곳이 없을 경우 옆으로 이동

 

 

1. Stack 또는 재귀 함수를 통해 구현

2. BFS보다 구현이 간결함

3. 검색 속도는 BFS에 비해 느림

 

탐색 경로를 결과로 출력한다고 하면, 재귀 함수를 통한 DFS의 파이썬 구현 코드는 다음과 같다.

# N×N 2차원 배열

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

# 방문한 노드일 경우 True / 방문하지 않은 노드일 경우 False
visited = [[False for _ in range(N)] for _ in range(N)]


def DFS(r, c):
    # 현재 탐색 중인 노드 (r, c)
    visited[r][c] = True
    
    route = []  # 탐색 경로 저장
    route.append((r, c))

    for i in range(4):
        # 인접 노드 (ny, nx)
        ny = r + dy[i]
        nx = c + dx[i]
        
        # 조건문을 통해 탐색 가능한 노드인지 확인
        if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
            route.append((ny, nx))
            DFS(ny, nx)  # 재귀
            
    return route

 

BFS와 DFS의 시간 복잡도

둘 다 조건 내의 모든 노드를 탐색하기 때문에 두 방식의 시간 복잡도는 동일하다.

 

N : 노드의 개수, E : 간선의 개수라고 했을 때

인접 리스트일 경우 O(N+E)

인접 행렬일 경우 O(N^2)로 동일하다.

 

BFS와 DFS를 사용하는 문제 유형

1. 모든 정점을 방문하는 것이 주요 문제일 경우

두 방식의 시간 복잡도는 동일하기 때문에 어느 것을 사용해도 무관하다.

 

2. 경로의 특징을 저장해야 하는 유형

(ex. 각 정점에 숫자가 적혀있고 경로에 같은 숫자가 있으면 안 되는 경우)

BFS로는 경로의 특징을 볼 수 없기 때문에 DFS를 사용한다.

 

3. 최단 거리를 구해야 하는 유형

BFS (가장 먼저 찾아지는 답이 최단 거리)

 

* 검색 대상 그래프가 크다면 DFS를 고려

* 검색 대상 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS 사용