[코드트리] BFS 최단거리 쉽게 이해하기 (개념부터 구현까지 총정리)

이번 6회차 미션은 알고리즘 개념을 하나 골라서 설명하는 글이다. 처음에는 DP로 할까도 생각했는데, 막상 글로 설명하려고 하니 너무 무거워질 것 같았다. 그래서 이번에는 BFS를 정리해 보려고 한다.

 

최단거리 찾기

 

 

BFS는 코딩테스트에서 자주 나오는 탐색 알고리즘이다. 특히 미로 찾기나 격자 탈출처럼 “최소 몇 번 움직이면 되는지”를 묻는 문제에서 자주 보인다.

 

이번에 기준으로 잡은 문제는 코드트리의 최소 경로로 탈출 하기 문제다.

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-escape-with-min-distance/description

최소 경로로 탈출 하기 설명 | 코드트리

 

 

BFS를 내가 이해한 방식

BFS는 너비 우선 탐색이라고 부른다. 이름만 보면 조금 딱딱한데, 나는 그냥 가까운 곳부터 확인하는 방식 이라고 이해했다.

 

격자에서 시작점이 하나 있다고 생각해 보면 쉽다. BFS는 시작점에서 바로 갈 수 있는 칸들을 먼저 본다. 그다음에는 거기서 한 칸 더 떨어진 칸들을 본다. 이런 식으로 한 번에 깊게 들어가는 게 아니라, 주변으로 퍼지면서 확인한다.

 

 

 

그래서 물결이 퍼지는 느낌이라고 많이 설명하는 것 같다. 시작점에서 1칸 거리, 2칸 거리, 3칸 거리 순서로 넓어진다.

이게 최단거리 문제에서 중요한 이유가 있다. 한 칸 이동할 때마다 비용이 똑같이 1이라면, 가까운 곳부터 보는 BFS에서는 도착점에 처음 도착했을 때가 가장 짧은 거리다. 더 긴 길이 먼저 나올 수가 없다.

 

 

문제를 그래프로 바꿔 생각하기

<최소 경로로 탈출 하기> 문제는 N×M 격자에서 왼쪽 위에서 시작해서 오른쪽 아래까지 가는 문제다. 중간에 뱀이 있는 칸은 지나갈 수 없고, 이동은 상하좌우로만 가능하다.

 

그래프 문제로 보기

 

처음에는 그냥 격자 문제처럼 보이지만, 사실 그래프 문제로 볼 수 있다.

 

각 칸은 하나의 정점이고, 상하좌우로 이동할 수 있다는 건 정점끼리 간선으로 연결되어 있다는 뜻이다. 그리고 한 번 이동할 때마다 비용은 1이다. 뱀이 있는 칸은 아예 갈 수 없는 정점이라고 보면 된다.

 

그러면 결국 이 문제는 시작점에서 도착점까지 가는 최소 이동 횟수를 구하는 문제가 된다. 이동 비용이 전부 같으니 BFS를 쓰기 좋은 형태다.

 

 

풀이 흐름

이 문제를 풀 때는 큐를 사용한다. 큐는 먼저 들어간 값이 먼저 나오는 구조라서, BFS처럼 가까운 곳부터 차례대로 확인하는 방식에 잘 맞는다.

 

처음에는 시작 위치인 (0, 0)을 큐에 넣는다. 그리고 방문했는지 확인하기 위한 visited 배열과, 각 칸까지 몇 번 이동해서 왔는지 저장하는 dist 배열을 준비한다.

 

큐에서 현재 위치를 하나 꺼낸 뒤, 상하좌우 네 방향을 확인한다. 이동하려는 위치가 격자 밖이면 안 되고, 뱀이 있는 칸이어도 안 된다. 이미 방문한 칸도 다시 볼 필요가 없다.

 

갈 수 있는 칸이라면 방문 처리하고, 현재 거리에서 1을 더한 값을 저장한 뒤 큐에 넣는다. 이 과정을 반복하면 BFS 순서대로 탐색이 진행된다.

 

핵심 코드는 아래처럼 작성할 수 있다.

from collections import deque

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

dist = [[-1] * m for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

q = deque()

if grid[0][0] == 1:
    q.append((0, 0))
    dist[0][0] = 0

while q:
    x, y = q.popleft()

    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 grid[nx][ny] == 0:
            continue

        if dist[nx][ny] != -1:
            continue

        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny))

print(dist[n - 1][m - 1])

 

여기서 grid[nx][ny] == 0인 경우는 뱀이 있는 칸이므로 지나가지 않는다. 반대로 1인 칸만 이동할 수 있다.

dist[nx][ny] = dist[x][y] + 1 부분은 현재 칸까지 온 거리에서 한 칸 더 이동했다는 뜻이다. 시작점의 거리를 0으로 두고 시작하기 때문에, 도착점의 dist 값이 최소 이동 횟수가 된다.

 

도착하지 못한 경우도 생각해야 한다. 거리 배열을 0으로 초기화하면, 실제 거리 0과 방문하지 못한 상태를 구분할 수 없다. 그래서 처음에는 -1로 초기화하고, 방문한 칸만 거리를 갱신하는 방식이 더 안전하다.

 

 

헷갈렸던 부분

BFS를 처음 볼 때 헷갈리는 건 DFS와의 차이다. DFS도 탐색이고 BFS도 탐색이라서, 둘 다 비슷하게 느껴질 수 있다.

 

하지만 최단거리 문제에서는 차이가 크다. DFS는 한 방향으로 끝까지 들어가는 방식이라서, 도착점에 먼저 도착해도 그게 최단거리라는 보장이 없다. 운 좋게 짧은 길을 먼저 찾을 수도 있지만, 알고리즘 자체가 최단거리를 보장해 주지는 않는다.

 

 

 

반면 BFS는 가까운 칸부터 확인한다. 그래서 이동 비용이 모두 같다면, 도착점에 처음 도착한 순간이 최단거리다. 이 차이를 알고 있어야 DFS로 억지로 최단거리를 구하려다 꼬이는 일을 줄일 수 있다.

 

또 하나 조심해야 할 부분은 방문 처리다. 방문 처리는 큐에서 꺼낼 때보다 큐에 넣을 때 바로 해주는 편이 좋다. 그래야 같은 칸이 큐에 여러 번 들어가는 일을 막을 수 있다.

 

좌표도 은근히 자주 틀린다. x, y라고 쓰면 편하긴 한데, 실제로는 행과 열을 의미한다. 그래서 nx, ny가 범위 안에 있는지 확인할 때 n, m을 반대로 쓰지 않도록 조심해야 한다.

 

 

풀고 나서 느낀 점

BFS는 코드만 보면 외울 게 많아 보인다. deque, visited, dist, dx, dy가 한 번에 나오니까 처음에는 그냥 공식처럼 느껴졌다.

 

그런데 이 문제를 격자에서 한 칸씩 퍼져 나가는 그림으로 생각하니 훨씬 이해가 쉬웠다. BFS는 단순히 큐를 쓰는 알고리즘이라기보다, 가까운 곳부터 본다 는 탐색 순서가 핵심이었다.

 

이번 문제도 결국 뱀을 피해서 오른쪽 아래까지 가는 문제였지만, 알고리즘 관점에서는 모든 이동 비용이 같은 최단거리 문제였다. 이걸 알아차리면 BFS를 선택하는 이유가 분명해진다.

 

앞으로 미로 탈출, 최소 이동 횟수, 격자에서 목적지까지 가기 같은 문제가 나오면 먼저 BFS를 떠올려 봐야겠다. 특히 이동 비용이 모두 1인지 확인하는 습관을 들이면, 어떤 문제에서 BFS를 써야 하는지 더 빨리 판단할 수 있을 것 같다.