[C++] BFS - 톰과 제리

풀이

일반적인 BFS와 다르게 단순 최단거리가 아닌, 방향을 최소한으로 바꾸는 횟수를 구해야 한다.

이때, 특이한 방법을 사용하는데 4방향에 대해서 while loop를 사용해 범위를 벗어나지 않거나, 벽이 아니거나, 이미 업데이트 되지 않은 위치라면 해당 위치를 업데이트 하는 것이다.

기존 BFS에서 1칸씩 이동하며 업데이트 했던 것과 달리, 한 방향에 대해 갈 수 있는 모든 위치를 한번에 업데이트 한다. 직진의 경우 방향이 바뀌지 않기 때문에 한번에 업데이트 할 수 있다. 또한,  BFS이므로 채워지지 않은 영역에 도달하는 최소 방향 전환 횟수를 구할 수 있다. 

단, 벽이 1로 표시되고 채워지지 않은 영역이 0이므로 벽과 방문지점을 구분하기 위해 시작점을 2로 하여 시작한다.

 

리뷰

처음에 한 지점에 대해 4방향으로 들어오는 체크 배열을 사용하는 방식으로 구현을 했었다. 

역시나 쉬운 방법은 존재했다..! 기존 BFS를 변형해 최소 방향 전환 횟수를 구하는 문제로 좋은 공부가 되었다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dr[4]={0, 1, 0, -1};
int dc[4]={1, 0, -1, 0};
bool ch[101][101][4];

struct Info{
    int row, col;
    Info (int a, int b){
        row=a;
        col=b;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("test.txt", "r", stdin); 

    int n, answer=100000;
    cin >> n;
    vector<vector<int>> map(n+1, vector<int> (n+1, 0));
  
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            cin >> map[i][j];
        }
    }
    int st_r, st_c, g_r, g_c;
    cin >> st_r >> st_c;
    cin >> g_r >> g_c;
    queue<Info> q;
    q.push(Info(st_r, st_c));
    map[st_r][st_c]=2;

    while (!q.empty()){
        Info v=q.front();
        q.pop();

        if (v.row == g_r && v.col==g_c) break;

        // 4방향 돌면서 같은 숫자로 채우기
        for (int i=0; i<4; i++){
            int nr=v.row;
            int nc=v.col;
            
            while (true){
                nr+=dr[i];
                nc+=dc[i];
                // 벽 만남
                if (nr<1 || nr>n || nc<1 || nc>n || map[nr][nc]==1) break;
                // 이미 채워진 경우 지나감
                if (map[nr][nc]>2) continue;
                // 0인 경우 +1로 채우기
                map[nr][nc] = map[v.row][v.col]+1;
                q.push(Info(nr, nc));
            }
        }
    }
    
    if (map[g_r][g_c]==0) cout << -1;
    else cout << map[g_r][g_c]-3;
    return 0;
}