C++로 구현하는 행렬 너비 우선 탐색(BFS) – 최단 거리 찾기

행렬에서의 너비 우선 탐색(BFS)이란?

2차원 행렬에서 임의의 칸(cell)은 왼쪽, 오른쪽, 아래, 위 네 방향으로 이동할 수 있습니다. 너비 우선 탐색(Breadth First Search, BFS)은 이러한 행렬에서 두 요소 사이의 최단 거리를 구하는 대표적인 그래프 탐색 알고리즘입니다.

각 칸은 다음과 같은 숫자 값으로 상태를 표현합니다.

• 2 : 해당 칸은 출발점(Source)입니다.
• 3 : 해당 칸은 도착점(Destination)입니다.
• 1 : 해당 칸은 어떤 방향으로든 이동할 수 있는 통로입니다.
• 0 : 해당 칸은 어떤 방향으로도 이동할 수 없는 장애물입니다.

이 규칙을 바탕으로 주어진 행렬에 대해 BFS를 수행하여 출발점에서 도착점까지의 최단 거리를 계산할 수 있습니다.

문제 해결 접근 방식

BFS를 사용해 행렬 전체를 탐색하고 두 칸 사이의 최소(최단) 거리를 찾는 알고리즘은 다음과 같습니다.

• 먼저 행(row)과 열(column) 크기를 입력받습니다.
• 입력받은 크기로 행렬을 초기화합니다.
• 정수형 함수 shortestDist(int row, int col, int mat[][col])는 행, 열, 행렬을 입력으로 받아 행렬 내 두 요소 사이의 최단 거리를 반환합니다.
• 출발점과 도착점을 찾기 위해 source와 destination 변수를 초기화합니다.
• 요소가 '3'이면 도착점으로, '2'이면 출발점으로 표시합니다.
• 주어진 행렬에 BFS를 적용하기 위해 큐(queue) 자료구조를 초기화합니다.
• 행렬의 행과 열 좌표를 쌍(pair) 형태로 큐에 삽입합니다. 이후 각 칸을 방문하며 해당 칸이 도착점인지 확인하고, 기존에 계산된 거리보다 더 짧은 경로가 있다면 거리 값을 갱신합니다.
• 다른 방향으로도 이동하며 현재 칸으로부터의 최소 거리를 계속 탐색합니다.
• 최종적으로 계산된 최단 거리를 결과로 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

int findDistance(int row, int col, int mat[][5]) {
    int source_i, source_j, destination_i, destination_j;

    // 행렬을 순회하며 출발점(2)과 도착점(3)의 좌표를 찾음
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == 2) {
                source_i = i;
                source_j = j;
            }
            if (mat[i][j] == 3) {
                destination_i = i;
                destination_j = j;
            }
        }
    }

    // 모든 칸의 거리를 무한대(INT_MAX)로 초기화
    int dist[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            dist[i][j] = INT_MAX;
    }

    // BFS를 시작하기 위한 큐 초기화
    queue<pair<int, int>> q;
    q.push(make_pair(source_i, source_j));
    dist[source_i][source_j] = 0;

    // 조건 검사를 추가한 변형된 BFS 수행
    while (!q.empty()) {
        // 큐 맨 앞 칸의 x 좌표(행) 정보 저장
        int x = q.front().first;
        // 큐 맨 앞 칸의 y 좌표(열) 정보 저장
        int y = q.front().second;
        // 해당 칸을 큐에서 제거
        q.pop();

        // 왼쪽으로 이동이 가능한 경우 (통로 또는 도착점)
        if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
            // 왼쪽 칸까지의 거리가 기존 계산된 경로보다 짧으면 갱신
            if (dist[x][y] + 1 < dist[x][y - 1]) {
                dist[x][y - 1] = dist[x][y] + 1;
                q.push(make_pair(x, y - 1));
            }
        }
        // 오른쪽으로 이동이 가능한 경우
        if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
            // 오른쪽 칸까지의 거리가 기존 계산된 경로보다 짧으면 갱신
            if (dist[x][y] + 1 < dist[x][y + 1]) {
                dist[x][y + 1] = dist[x][y] + 1;
                q.push(make_pair(x, y + 1));
            }
        }
        // 위쪽으로 이동이 가능한 경우
        if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
            if (dist[x][y] + 1 < dist[x - 1][y]) {
                dist[x - 1][y] = dist[x][y] + 1;
                q.push(make_pair(x - 1, y));
            }
        }
        // 아래쪽으로 이동이 가능한 경우
        if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
            // 아래쪽 칸까지의 거리가 기존 계산된 경로보다 짧으면 갱신
            if (dist[x][y] + 1 < dist[x + 1][y]) {
                dist[x + 1][y] = dist[x][y] + 1;
                q.push(make_pair(x + 1, y));
            }
        }
    }
    return dist[destination_i][destination_j];
}

int main() {
    // 행과 열의 개수 초기화
    int row = 5;
    int col = 5;
    // 행렬 초기화
    int mat[][5] = {
        {1, 0, 0, 2, 1},
        {1, 0, 1, 1, 1},
        {0, 1, 1, 2, 0},
        {3, 1, 0, 0, 1},
        {1, 1, 0, 0, 1}
    };
    int answer = findDistance(row, col, mat);
    // 출발점과 도착점이 연결되어 있지 않은 경우
    if (answer == INT_MAX)
        cout << "No Path Found" << endl;
    else {
        cout << "출발점과 도착점 사이의 최단 거리:" << endl;
        cout << answer << endl;
    }
    return 0;
}

실행 결과

출발점과 도착점 사이의 최단 거리: 4

정리

이 알고리즘은 BFS의 특성상 가중치가 없는 격자(grid)에서 항상 최단 경로를 보장합니다. 시간 복잡도는 행렬의 모든 칸을 최대 한 번씩 방문하므로 O(row × col)이며, 공간 복잡도 역시 거리 배열과 큐를 위해 O(row × col)입니다. 만약 출발점에서 도착점에 도달할 수 없다면 거리 값이 INT_MAX로 남아 있으므로, 이를 확인하여 "경로 없음"을 출력하는 것도 중요한 처리 포인트입니다.