[BOJ] 직사각형 탈출 16973번 C++

문제

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

입력

첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

출력

첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

 

접근 방식

 

생각보다 간단하다

BFS 방식으로 풀면서 최소 이동 거리를 구하면 되는데

중요한 것은 이동시마다 직사각형이 격자판 내부에 있는지, 벽이 있는 칸에 있는지를 확인해야 한다.

 

이때, 처음에 직사각형의 모든 칸을 벽이 있는 칸인지 확인해주었는데 시간초과가 발생하였다.

따라서, 이동하는 방향마다

아래로 내려간다면 가장 아래줄만 다시 검사하면 되기 때문에 이를 수정해서 해결해주었다.

 

코드

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

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int mat[1002][1002], visited[1002][1002];
queue<pair<int,int>> q;


bool checkCanGo(int H, int W, int nx, int ny, int r) {
    if(r == 0) {
        for(int j = ny; j < ny + W; j++){ // 아래로 이동
            if(mat[nx + H - 1][j] == 1) return false;
        }
    }
    else if (r == 1) {  // 오른쪽으로 이동
        for (int i = nx; i < nx + H; i++) {
            if (mat[i][ny + W - 1] == 1) return false;
        }
    } else if (r == 2) {  // 위로 이동
        for (int j = ny; j < ny + W; j++) {
            if (mat[nx][j] == 1) return false;
        }
    } else if (r == 3) {  // 왼쪽으로 이동
        for (int i = nx; i < nx + H; i++) {
            if (mat[i][ny] == 1) return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N,M, H, W, Sr, Sc, Fr, Fc;

    cin>>N>>M;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            cin>>mat[i][j];
        }
    }

    memset(visited, -1, sizeof(visited));

    cin>>H>>W>>Sr>>Sc>>Fr>>Fc;


    q.push({Sr, Sc});
    visited[Sr][Sc] = 0;


    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int r = 0; r < 4; r++) {
            int nx = x + dx[r];
            int ny = y + dy[r];

            if(nx <= 0 || ny <= 0 || nx > N || ny > M || visited[nx][ny] != -1 || mat[nx][ny] == 1) continue;
            if(nx + H-1 > N || ny + W - 1 > M) continue;
            if(checkCanGo(H, W, nx, ny, r)) {
                visited[nx][ny] = visited[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    cout<<visited[Fr][Fc];

}