Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 이진 행렬 최단 경로 문제 (BFS 알고리즘)

문제 소개

N×N 크기의 정사각형 격자(grid)가 주어지며, 각 칸은 비어 있는 경우(0)와 막혀 있는 경우(1)로 나뉩니다. 왼쪽 위에서 오른쪽 아래로 이어지는 '명확한 경로(clear path)'는 길이가 k일 때 다음 조건을 만족하는 셀 C1, C2, ..., Ck로 정의됩니다.

  • 인접한 두 셀 Ci와 Ci+1은 8방향으로 연결되어 있어야 합니다. 즉, 서로 다른 셀이면서 변 또는 모서리를 공유합니다.
  • C1은 위치 (0, 0)에 있어야 합니다.
  • Ck는 위치 (N-1, N-1)에 있어야 합니다.
  • Ci가 (r, c)에 위치할 때, grid[r][c]의 값은 반드시 0(비어 있음)이어야 합니다.

목표는 왼쪽 위에서 오른쪽 아래까지 이어지는 가장 짧은 명확한 경로의 길이를 구하는 것이며, 가능한 경로가 존재하지 않는다면 -1을 반환해야 합니다.

예시

예를 들어 격자가 다음과 같이 주어졌다고 가정해 보겠습니다.

000
110
110

주황색으로 표시된 셀들이 선택한 경로에 해당하며, 이 경로의 길이는 4입니다.

풀이 접근 방법

이 문제는 가중치가 없는 그래프에서 최단 거리를 구하는 전형적인 상황이므로, BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. BFS는 시작 지점에서 가까운 셀부터 순서대로 탐색하기 때문에 목표 지점에 처음 도달했을 때의 거리가 곧 최단 거리가 됩니다.

구체적인 풀이 단계는 다음과 같습니다.

  • 8방향 이동을 나타내는 방향 배열을 정의합니다. 배열은 [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,-1], [-1,0]]처럼 8개의 좌표 쌍을 담습니다.
  • 메인 함수는 격자(grid)를 입력으로 받아 아래 과정을 수행합니다.
  • 점(point)을 저장할 큐 q를 선언하고, n에는 행의 개수를 저장합니다.
  • grid[0][0]의 값이 0이라면 새로운 점 p(0, 0, 1)를 생성해 q에 삽입하고, grid[0][0]을 1로 변경하여 방문 처리를 합니다.
  • q가 빌 때까지 다음을 반복합니다.
    • q의 맨 앞 점을 curr로 가져오고, 해당 점을 큐에서 제거합니다.
    • curr에서 x, y, c 값을 각각 추출합니다.
    • x = n-1이고 y = n-1이라면(오른쪽 아래 도착 지점 도달), c를 반환합니다.
    • c를 1 증가시킵니다.
    • i를 0부터 7까지 반복하면서 다음을 수행합니다.
      • X := x + d[i][0], Y := y + d[i][1]로 다음 이동 좌표를 계산합니다.
      • X와 Y가 격자 범위 안에 있고 grid[X][Y]의 값이 0이라면, grid[X][Y]를 1로 바꿔 방문 처리하고 새로운 점 p(X, Y, c)를 q에 삽입합니다.
  • 큐가 모두 비었는데도 도착 지점에 도달하지 못했다면 -1을 반환합니다.

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
    int x, y, c;
    point(int a, int b, int z){
        x = a;
        y = b;
        c = z;
    }
};
class Solution {
    public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue <point> q;
        int n = grid.size();
        if(!grid[0][0]){
            q.push(point(0, 0, 1));
            grid[0][0] = 1;
        }
        while(!q.empty()){
            point curr = q.front();
            q.pop();
            int x = curr.x;
            int y = curr.y;
            int c = curr.c;
            if(x == n-1 && y == n-1)return c;
                c++;
            for(int i = 0; i < 8; i++){
                int X = x + d[i][0];
                int Y = y + d[i][1];
                if(X >= 0 && X < n && Y >= 0 && Y < n &&
                !grid[X][Y]){
                    grid[X][Y] = 1;
                    q.push(point(X, Y, c));
                }
            }
        }
        return -1;
    }
};
main(){
    vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
    Solution ob;
    cout << (ob.shortestPathBinaryMatrix(v));
}

입력

[[0,0,0],[1,1,0],[1,1,0]]

출력

4