[백준] 16973 직사각형 탈출 (C++)

문제

원문 링크 : https://www.acmicpc.net/problem/16973

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

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

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

풀이 및 구현

예제 1번으로 예를 들어보자.

크기가 HxW인 직사각형을 빨간색 사각형이라고 한다면, 빨간색 사각형의 위치를 왼쪽 그림에서 오른쪽 그림으로 이동해야 한다.

이때 중간에 있는 검은색 사각형이 벽이기 때문에 빨간색 사각형을 오른쪽으로 밀어서 이동할 수 없고 그림과 같이 아래로 돌아가야 한다.

따라서 총 이동 횟수는 7번이 된다.

직사각형의 이동 방향에 벽이 없거나, 격자판을 벗어나지 않을 때만 직사각형을 움직여준다면 BFS로 간단하게 해결할 수 있다.

위의 그림과 같이 이동하려는 방향에 따라 파란색 부분이 격자판을 벗어나지 않고, 전부 0일 때 아래 ismovable 함수에서 true를 반환해주었다.

bool ismovable(int d, int x, int y) {
    // 위
    if (d == 0) {
        if (x - 1 < 0) return false;
        for (int i = 0; i < W; i++) {
            if (board[x - 1][y + i]) return false;
        }
    }
    // 오른쪽
    else if (d == 1) {
        if (y + W >= M) return false;
        for (int i = 0; i < H; i++) {
            if (board[x + i][y + W]) return false;
        }
    }
    // 아래
    else if (d == 2) {
        if (x + H >= N) return false;
        for (int i = 0; i < W; i++) {
            if (board[x + H][y + i]) return false;
        }
    }
    else {
        if (y - 1 < 0) return false;
        for (int i = 0; i < H; i++) {
            if (board[x + i][y - 1]) return false;
        }
    }
    return true;
}

직사각형의 위치는 왼쪽 상단 모서리의 점을 유지해주면서 해당 방향으로 이동 가능하고, 아직 방문하지 않은 지점들에 대해 모두 탐색한다면
시간복잡도는 $O((N - H) * (M - W) * max(H, W))$이고, 제한시간이 2초이기 때문에 시간 내에 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int N, M, W, H, sx, sy, fx, fy;
vector<vector<int>> board;

bool ismovable(int d, int x, int y) {
    // 위
    if (d == 0) {
        if (x - 1 < 0) return false;
        for (int i = 0; i < W; i++) {
            if (board[x - 1][y + i]) return false;
        }
    }
    // 오른쪽
    else if (d == 1) {
        if (y + W >= M) return false;
        for (int i = 0; i < H; i++) {
            if (board[x + i][y + W]) return false;
        }
    }
    // 아래
    else if (d == 2) {
        if (x + H >= N) return false;
        for (int i = 0; i < W; i++) {
            if (board[x + H][y + i]) return false;
        }
    }
    else {
        if (y - 1 < 0) return false;
        for (int i = 0; i < H; i++) {
            if (board[x + i][y - 1]) return false;
        }
    }
    return true;
}

int BFS() {
    queue<tuple<int, int, int>> q;
    vector<vector<int>> visited(N, vector<int>(M));
    q.push({sx - 1, sy - 1, 0});
    while (!q.empty()) {
        auto[x, y, cnt] = q.front();
        q.pop();

        if (x == fx - 1 && y == fy - 1) return cnt;

        for (int k = 0; k < 4; k++) {
            if (ismovable(k, x, y)) {
                int i = x + dx[k];
                int j = y + dy[k];
                if (!visited[i][j]) {
                    visited[i][j] = 1;
                    q.push({i, j, cnt + 1});
                }
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    board.assign(N, vector<int>(M));
    for (auto& i : board) for (int& j : i) cin >> j;
    cin >> H >> W >> sx >> sy >> fx >> fy;

    cout << BFS();
}

후기

보통 BFS를 할 때 점을 이동시키는 문제들은 많이 풀어봤었는데 도형을 이동시키는 문제는 잘 안풀어봤던 것 같다. 이동 방향에 벽이 있는지 검사를 구현할 때 조심한다면 무난한 BFS문제라고 생각한다.