[Algorithm] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

탐색(Search)은 보통 많은 양의 데이터중에서 원하는 데이터를 찾는 것을 의미합니다.

프로그래밍에서는 그래프, 트리 등의 자료구조(Data structure)를 이용하여 탐색을 구현합니다.

탐색 방법 중 대표적인 것이 바로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)입니다.

 

DFS와 BFS를 구현하는 자료구조인 스택(Stack), 큐(Queue), 그래프(Graph)와 재귀 함수(Recursive Function)에 대한 설명은 생략하겠습니다.

 

DFS는 그래프 탐색 과정에서 최대한 깊숙이 들어가서 노드를 방문한 후(리프 노드까지), 다시 돌아가 탐색하는 알고리즘입니다.

DFS의 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 함.

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함.

DFS

 

DFS는 다음과 같이 구현할 수 있습니다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

graph는 각 노드의 간선을 나타내며, 그래프를 그림으로 표현하면 다음과 같습니다.

DFS는 스택을 직접적으로 사용해도 되지만 위와 같이 재귀 호출만 사용하여 통해 쉽게 구현할 수 있습니다.

print(v, end=' ')을 통해 방문한 노드의 순서를 출력하면 1 2 7 6 8 3 4 5가 됩니다.

DFS의 시간 복잡도는 O(N)입니다.

 

다음으로 BFS는 가까운 노드부터 탐색하는 알고리즘입니다.

DFS는 스택 또는 재귀 호출을 사용해 구현한 반면, BFS는 큐를 사용합니다.

 

BFS의 동작 과정은 다음과 같습니다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리함.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리함.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함.

 

BFS

 

BFS는 다음과 같이 구현할 수 있습니다.

from collections import deque


def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

그래프를 그림으로 표현하면 다음과 같습니다.

print(v, end=' ')을 통해 방문한 노드의 순서를 출력하면 1 2 3 8 7 4 5 6이 됩니다.

BFS의 시간 복잡도는 DFS와 마찬가지로 O(N)입니다.

 

코딩테스트에서는 2차원 배열에서 탐색 문제를 그래프로 변환하고 DFS, BFS로 풀어낼 수 있습니다.

 

보통 DFS는 완전 탐색 문제를, BFS는 최단 경로 문제를 풀어낼 때 사용됩니다.

다른 탐색 문제는 둘 중 아무거나 사용해도 거의 차이가 없습니다.

 

그러면 DFS를 이용하여 '음료수 얼려 먹기' 문제를 풀어보겠습니다.

<문제>

<해설>

DFS 함수를 만들고, 탐색 방법을 좌, 우, 상, 하로 변경하여 구현하면 됩니다.

 

<구현>

n = 4
m = 5

graph = [[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]


def solution(n, m, graph):
    # 모든 노드(위치)에 대하여 음료수 채우기
    result = 0
    for i in range(n):
        for j in range(m):
            # 현재 위치에서 DFS 수행
            if dfs(i, j) is True:
                result += 1

    return result


# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False


result = solution(n, m, graph)
print('result: {0}'.format(result))

 

추가로 BFS를 이용하여 '미로 탈출' 문제를 풀어보겠습니다.

<문제>

<해설>

BFS 함수를 만들고, 앞의 방법과 같이 탐색 방법을 좌, 우, 상, 하로 변경하여 구현하면 됩니다.

 

<구현>

from collections import deque

n = 5
m = 6

graph = [[1, 0, 1, 0, 1, 0], [1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def solution(n, m, graph):
    return bfs(0, 0)


# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]


result = solution(n, m, graph)
print('result: {0}'.format(result))

 

참고: https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2821s