[알고리즘 이론] 5. 너비 우선 탐색(BFS)

안녕하세요? 닉네임간편입니다. 이번 시간에는 너비 우선 탐색에 대해 알아보겠습니다.

1. 너비 우선 탐색이란?

너비 우선 탐색(Breadth-First Search)은 시작점에서 가까운 정점 순서대로 탐색을 하는 알고리즘입니다. 

위 그림을 예시로 들어 설명하겠습니다. 시작점은 정점 1이며, 동일한 거리에 있다면 왼쪽부터 방문하도록 하겠습니다.

1) 1 -> 2 -> 3

정점 1에 인접한 정점 2와 3을 먼저 방문합니다. 정점 3을 방문한 이후 정점 1에 인접한 간선이 없으므로 해당 단계의 탐색을 종료합니다.

2) 3 -> 4 -> 5 -> 6

정점 2와 3에 인접한 정점을 왼쪽부터 순서대로 방문합니다. 정점 6을 방문한 이후 정점 2, 3에 인접한 간선이 없으므로 이 단계의 탐색을 종료합니다.

3) 6 -> 7 -> 8 -> 9 -> 0

정점 4, 5, 6 각각에 인접한 정점 7, 8, 9, 0을 순서대로 방문합니다. 이후 더 이상 방문할 정점이 없으므로 탐색을 종료합니다.

DFS가 한 분기 탐색을 깊게 했다면, 너비 우선 탐색은 현재 정점에 인접해있는 모든 정점을 먼저 방문하고, 방문했던 정점들에 인접해있는 모든 정점을 검사합니다. 즉, 보이시는 바와 같이 정점을 넓게 탐색합니다.

2. 너비 우선 탐색의 구현

너비 우선 탐색은 큐를 이용해 구현합니다. 앞선 그림을 다시 가져와서 설명하겠습니다.

또 등장한 BFS 예시

1) 먼저 각 깊이의 정점들을 방문할 때마다 모든 인접한 정점을 검사합니다. 이들을 방문하면서 만일 어떤 정점이 아직 방문하지 않은 정점으로 가는 간선을 갖고 있다면, 이 정점을 방문할 것임을 표시한 다음 큐에 저장합니다.

예를 들어 정점 2를 방문하고 있는 와중에 아직 방문되지 않은 정점 4와 5로 가는 간선이 발견되었다면, 이곳을 방문할 '예정'임을 표시한 다음 큐에 저장합니다. 이후 정점 3을 방문합니다. 정점 3에서도 정점 6에 방문 예정을 표시한 다음 큐에 저장합니다.

2) 앞서 모든 정점을 방문했다면 이제 큐에 저장되었던 '방문 예정'인 정점들에 대해서 방문을 시작합니다.

즉, 앞서 깊이 2에서 정점 2와 3을 방문한 이후, 그때 '방문 예정'으로 표시했던 정점 4와 5, 그리고 6은 큐에 저장되어 있습니다. 이제 큐에서 하나하나 순서대로 꺼내면서 해당 정점에 인접한 모든 정점을 방문합니다.

자료구조 중 큐를 사용한 이유는 바로 이것 때문입니다. 먼저 방문된 순서대로 다시 방문을 진행해야 하기 때문에, 선입선출형 자료구조인 큐가 적합합니다. 따라서 큐를 사용해 너비 우선 탐색을 구현합니다.

3. 너비 우선 탐색의 시간 복잡도

깊이 우선 탐색과 마찬가지로 그래프 표현 방식에 따라 시간 복잡도에 차이가 있습니다.

1) 인접 행렬

모든 정점을 한 번씩 탐색하면서, 각 정점에 대해서 연결된 모든 간선에 대해서 탐색하기 때문에 총 시간 복잡도는 O(|V|^2)이 됩니다.

2) 인접 리스트

모든 정점을 한 번씩 탐색하며, 정점을 탐색할 때마다 인접해있는 모든 간선을 탐색하기 때문에 총 시간 복잡도는 O(|V| + |E|)가 됩니다.

4. 장점

너비 우선 탐색은 깊이 별로 모든 정점을 탐색하기 때문에 목표 노드를 찾기까지의 최단 경로를 구할 수 있습니다. 따라서 너비 우선 탐색은 모든 정점을 검사하면서 탐색하는 작업엔 잘 사용하지 않고 이 경우 DFS를 사용합니다.

물론 이는 간선에 주는 가중치가 없는 그래프에 한하며, 가중치가 있는 그래프의 경우 다익스트라 알고리즘을 적용합니다.

5. 단점

1) 탐색 경로가 매우 길 경우 큐에 많은 정보를 저장해야 합니다. 따라서 DFS에서보다 많은 저장 공간을 필요로 하기 때문에 메모리 초과가 발생할 수도 있습니다.

2) 최악의 경우 모든 정점을 탐색하게 됩니다. 즉, 해가 가장 깊은 곳에 위치해있다면 DFS로 모든 정점을 탐색한 것과 차이가 없게 됩니다.

6. 예시

문제는 [백준] 2178번-미로탐색 문제입니다.

[문제 링크]

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

미로 탐색은 탈출할 수 있는 최단 경로를 찾는 문제이므로, 탐색 알고리즘 중에서도 너비 우선 탐색을 사용했습니다. 또한 한 지점에서 상하좌우로 탐색해야 하기 때문에 인접 행렬로 그래프를 표현했습니다.

또한 파이썬에서는 일반적인 큐를 사용하기보단 덱(deque)을 사용합니다. 덱은 양방향 큐이며 일반적인 큐가 데이터를 추가한 순서대로 데이터를 추출할 수 있다면, 덱은 데이터를 양방향에서 추가하고 추출할 수 있습니다.

파이썬에도 일반적인 큐(Queue)가 있기는 하지만 이 자료구조는 멀티 스레드를 대비한 것이기 때문에 단일 스레드 하에선 덱보다 느립니다. 따라서 BFS를 적용할 때에도 덱을 사용합니다.

이 문제는 다음과 같이 접근합니다.

1) 우선 처음 시작 좌표를 덱에 넣습니다. 이 좌표부터 탐색을 시작합니다.

2) 이후 이 좌표에 대해서 상하좌우로 이동한 좌표에 대해서 검사하고, 해당 좌표로 이동이 가능하다면 '방문 예정' 여부를 확인한 후 덱에 넣습니다.

3) 해당 좌표에 대한 탐색이 종료되었다면 이제 덱에 있는 다른 좌표에 대해서 앞선 동작을 반복합니다. 이를 통해 최종적으로 탈출에 걸린 최소 횟수를 찾습니다.

이때 입력은 모두 탈출이 가능한 경우만 주어지므로, 예외 상황은 고려하지 않았습니다.

a) 전체 링크

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
maze = [list(input().rstrip()) for _ in range(N)]


def bfs():
    dq = deque()
    dq.append((0, 0, 1))
    visited = [[False] * M for _ in range(N)]
    visited[0][0] = True
    while dq:
        y, x, d = dq.popleft()
        if y == N-1 and x == M-1:
            return d
        nd = d + 1
        for m in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ny = y + m[0]
            nx = x + m[1]
            if 0 <= ny < N and 0 <= nx < M and maze[ny][nx] == '1' and not visited[ny][nx]:
                visited[ny][nx] = True
                dq.append((ny, nx, nd))


print(bfs())

b) 미로 입력받기

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
maze = [list(input().rstrip()) for _ in range(N)]

미로 배열을 입력받은 후 생성합니다. 이때 input() 뒤에 rstrip()을 해주지 않으면 개행 문자까지 입력받기 때문에 오류가 생길 수 있습니다. 따라서 rstrip()을 꼭 해주셔야 합니다.

또한 bfs() 메서드에서 덱을 사용할 것이므로 import 해줍니다.

c) bfs() 메서드 정의 및 출력

def bfs():
    dq = deque()
    dq.append((0, 0, 1))
    visit = [[False] * M for _ in range(N)]
    visit[0][0] = True
    while dq:
        y, x, d = dq.popleft()
        if y == N-1 and x == M-1:
            return d
        nd = d + 1
        for m in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ny = y + m[0]
            nx = x + m[1]
            if 0 <= ny < N and 0 <= nx < M and maze[ny][nx] == '1' and not visit[ny][nx]:
                visit[ny][nx] = True
                dq.append((ny, nx, nd))
print(bfs())

1) 덱 및 탐색 배열 생성

먼저 덱을 생성한 후 초기 좌표인 (0,0)과 시도 횟수 1을 추가합니다. 문제에선 (1,1)부터 (N, M)으로 이동하지만, 컴퓨터에선 입력상 0부터 시작하기에 이를 (0,0)부터 (N-1, M-1)로 바꾸어서 풀어보겠습니다.

다음으로 방문 예정 여부를 확인하는 visit 배열을 생성한 후, 초기 좌표를 탐색했음(True)로 설정합니다. 이때 visit은 방문 예정 여부를 확인하는 것이며, 앞서 DFS 메서드를 정의할 때 '방문 여부'를 확인하는 배열을 생성하였던 것과는 차이가 있습니다. 너비 우선 탐색의 경우 방문할 예정인 요소들을 큐에 추가한 다음 먼저 추가된 순서대로 다시 탐색을 진행하기 때문에 이미 방문한 것은 아닙니다. 다만, 방문 예정 여부를 확인하지 않을 경우 중복될 가능성이 존재하기 때문에 확인을 할 수 있도록 '방문 예정 여부'를 확인하는 배열을 만듭니다.

2) 답을 찾을 때까지 반복

while문을 통해 덱에 요소가 남아있을 때까지 탐색하도록 합니다.

먼저 덱에서 좌표와 시도 횟수인 y, x, d를 꺼냅니다. 만일 y와 x가 각각 N-1, M-1이라면 탈출에 성공한 것이므로 시도 횟수인 d를 반환하고, 그렇지 않다면 다음 동작을 수행합니다.

3) 상하좌우 이동

상하좌우로 이동하기 전 시도 횟수가 1 증가하므로 nd를 d+1로 정의합니다.

이후 상, 하, 좌, 우 좌표에 대해서 새로운 좌표 (ny,nx)를 만든 후, 이것이 배열 범위 내에 있고, 이 좌표가 미로 배열에서 1의 값(이동할 수 있는 칸)에 해당하며, 아직 탐색하지 않았다면 덱에 이 좌표를 추가합니다. 그리고 방문 예정 여부 배열을 True로 설정한 후, 다음 새로운 (ny,nx)에 대해서 동작을 반복합니다.

이를 통해 한 좌표에서 상하좌우로 이동하면서 미로를 탈출하는 최소 경로를 찾습니다.

4) 결과

7. 마무리

이번 시간에는 너비 우선 탐색에 대해서 알아보았습니다. 혹시라도 궁금하신 점이 있으시다면 언제든지 댓글로 남겨주시길 바랍니다.

그럼 긴 글 읽어주셔서 감사합니다.