[PG/C++] 프로그래머스 Lv3 - 블록 이동하기

https://school.programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

문제 설명

이렇게 board가 주어져 있다면, 빈칸 (0)에서만 로봇을 움직여 (n -1, m -1) 로 가야한다. 갈 수 있는 모든 경우의 수에서 최단 시간을 구하면 된다. 일반적인 BFS 문제와 다르게 로봇은 두 칸을 차지하고, 회전이 가능하다는 점이 특징이었다.

로봇은 어느 방향으로든 90도 회전이 가능하나, 이동하는 방향의 대각선 칸이 벽(1)이라면 회전할 수 없다.

모든 움직임에는 1초의 시간이 걸린다.

해결 과정

board의 모든 칸을 정점으로 보고 BFS를 수행하여 최단 시간을 구한다. 평범하게 네 방향으로 움직던 것과 달리, 여기에서는 회전할 수 있는 모든 경우를 함께 고려해주어야 한다. 또한, 여기에서는 로봇이 두 칸을 차지하고 있으므로 가로 방향일 때는 왼쪽 칸을, 세로 방향일 때는 위쪽 칸을 기준으로 하여 dist에 저장해주었다.

회전할 수 있는 방향은 현재 로봇이 가로 방향으로 있을 때와 세로 방향으로 있을 때 각각 네 가지이다. 그 이유를 아래에서 그림으로 설명해보겠다.

빨간색으로 빗금친 곳이 현재 로봇의 위치라고 할 때, 가로 방향으로 되어있는 로봇이 회전할 수 있는 범위이다. 녹색으로 칠한 곳이 모두 빈 칸이어야만 로봇은 1번, 2번 위치로 회전이 가능하다. 1번 위치로 회전하기 위해서는 (y - 1, x + 1) 칸이 비어있어야 하고, 2번 위치로 이동하기 위해서는 (y - 1, x) 칸이 비어있어야 하기 때문이다. 보라색으로 칠한 곳도 마찬가지이다.

세로 방향으로 되어있는 로봇도 함께 보자.

역시 녹색 위치가 전부 빈 칸이고, 보라색 칸이 전부 빈칸이어야만 그 방향으로 회전이 가능하다.

나는 flag 라는 bool 타입의 변수를 넣어서 가로 방향이면 0, 세로 방향이면 1이 되도록 하였다. dist도 dist[2][101][101]로 크기를 맞춰서 같은 (y, x) 위치에 있더라도 가로, 세로 방향의 여부에 따라 로봇이 다른 위치에 있음을 표시해주었다.

가로, 세로 방향을 고정시켜 네 방향으로 이동해주는 경우를 탐색하고, 회전할 수 있는 네 가지 경우를 추가로 탐색하였다. 회전할 때는 회전하고자 하는 방향이 board 의 크기 안에 있고, 빈 칸이어야 하므로 이를 예외처리하였다.

소스 코드

#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

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

int solution(vector<vector<int>> board) {
    memset(dist, -1, sizeof(dist));
    int n = board.size(), m = board[0].size();

    queue<tuple<bool, int, int>> q;  // 0이면 가로, 1이면 세로
    q.push(make_tuple(0, 0, 0));
    dist[0][0][0] = 0;
    while (!q.empty()) {
        bool flag; int y, x; tie(flag, y, x) = q.front(); q.pop();

        if (flag == 0) { // 가로 방향
            for (int direction = 0; direction < 4; direction++) {
                int ny = y + dy[direction], nx = x + dx[direction];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m - 1) continue;
                if (dist[flag][ny][nx] == -1 && board[ny][nx] == 0 && board[ny][nx + 1] == 0) {
                    q.push(make_tuple(flag, ny, nx));
                    dist[flag][ny][nx] = dist[flag][y][x] + 1;
                }
            }

            if(y > 0 && board[y - 1][x] == 0 && board[y - 1][x + 1] == 0){
                if(dist[1][y-1][x] == -1){
                    q.push(make_tuple(1, y -1, x)); 
                    dist[1][y -1][x] = dist[flag][y][x] + 1; 
                }
                if(dist[1][y - 1][x + 1] == -1){
                    q.push(make_tuple(1, y - 1, x+ 1)); 
                    dist[1][y - 1][x + 1] = dist[flag][y][x] + 1; 
                }
            }
            if(y < n - 1 && board[y + 1][x] == 0 && board[y + 1][x + 1] == 0){
                if(dist[1][y][x] == -1){
                    q.push(make_tuple(1, y, x)); 
                    dist[1][y][x] = dist[flag][y][x] +1; 
                }
                if(dist[1][y][x + 1] == -1){
                    q.push(make_tuple(1, y, x + 1)); 
                    dist[1][y][x + 1] = dist[flag][y][x] + 1; 
                }
            }
        }
        else { // 세로 방향 
            for (int direction = 0; direction < 4; direction++) {
                int ny = y + dy[direction], nx = x + dx[direction];
                if (ny < 0 || ny >= n - 1 || nx < 0 || nx >= m) continue;
                if (dist[flag][ny][nx] == -1 && board[ny][nx] == 0 && board[ny + 1][nx] == 0) {
                    q.push(make_tuple(flag, ny, nx));
                    dist[flag][ny][nx] = dist[flag][y][x] + 1;
                }
            }

            if(x > 0 && board[y][x - 1] == 0 && board[y + 1][x - 1] == 0){
                if(dist[0][y][x-1] == -1){
                    q.push(make_tuple(0, y, x- 1)); 
                    dist[0][y][x -1] = dist[flag][y][x] + 1; 
                }
                if(dist[0][y + 1][x - 1] == -1){
                    q.push(make_tuple(0, y+ 1, x -1)); 
                    dist[0][y + 1][x -1] = dist[flag][y][x] + 1; 
                }
            }
            if(x < m - 1 && board[y][x + 1] == 0 && board[y + 1][x + 1] == 0){
                if(dist[0][y][x] == -1){
                    q.push(make_tuple(0, y, x)); 
                    dist[0][y][x] = dist[flag][y][x] + 1; 
                }
                if(dist[0][y + 1][x] == -1){
                    q.push(make_tuple(0, y + 1, x)); 
                    dist[0][y + 1][x] = dist[flag][y][x] + 1;
                }
            }
        }
    }
    int cand1 = dist[0][n - 1][m - 2];
    int cand2 = dist[1][n - 2][m - 1];
    if (cand1 != -1 && cand2 != -1)
        return min(cand1, cand2);
    else if (cand1 == -1)
        return cand2;
    else if (cand2 == -1)
        return cand1;
}