[프로그래머스] 블록 이동하기

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

최소 거리 찾기이므로 BFS로 해결할 수 있지만 로봇이 2칸을 차지한다는 점, 로봇이 회전 가능하다는 점을 유의해야해서 상당히 까다로운 문제이다.
로봇을 구현하기 위해서 규칙을 설정하였다.

1. 로봇이 가로방향인 경우 로봇의 왼쪽부분의 좌표를 저장한다.
2. 로봇이 세로방향인 경우 로봇의 위쪽부분의 좌표를 저장한다.

즉, 아래와 같은 그림의 경우 로봇의 방향은 가로방향으로, 로봇의 좌표는 (0, 0)을 저장한다는 것이다.

로봇을 좌표를 표현할 방식을 결정함으로써 로봇의 회전을 구현하기가 한결 수월해진다. 로봇의 회전을 구현하기에 앞서 회전 가능한지 확인해야한다.
로봇이 회전 가능한 경우는 결국 2x2 크기의 정사각형의 값들이 모두 0이어야 한다.

따라서 2x2 크기의 정사각형을 확인하는 canRotate(int x, int y) 함수를 만들어서 검사하였다.
이 때 x, y의 값은 2x2 정사각형에서 좌측 상단 좌표로 구현하였다.

로봇을 회전하는 경우는 가로 방향일 때 4가지, 세로 방향일 때 4가지로, 총 8가지의 경우가 있다. 회전을 구현하기 위한 규칙을 정해두었기 때문에 그리 어렵지 않게 구현할 수 있다.

우선 가로 방향일 때, 오른쪽 점을 축으로 하여 위로 회전하는 경우를 살펴보자.

가로방향인 로봇의 좌표는 왼쪽부분을 저장한다고 정했으므로 위 그림에서 노란색 부분은 로봇의 좌표이다. 빨간색 부분은 로봇이 회전할 수 있는지 확인할 때 검사해야하는 2x2 정사각형의 좌측 상단에 해당하는 부분이다. 따라서 노란색 부분의 좌표를 (x, y)라고 하면 회전 가능한지 여부를 canRotate(x, y-1)로 검사해야한다.

회전하고 난 후의 모습을 보자. 회전 하기 전의 로봇의 좌표를 노란색으로, 회전 후 로봇의 좌표를 초록색으로 표시하였다. 노란색 부분의 좌표는 (x, y)이므로 초록색 부분의 좌표는 (x+1, y-1)이 된다. 따라서 이 경우 queue에 (x+1, y-1)을 저장하여 BFS를 진행하면 된다.

나머지 방향에 대해서도 위와 같은 방식으로 구현하면 쉽게 로봇의 회전을 구현할 수 있다.

마지막으로 BFS를 진행하면서 중복 체크를 위한 visited배열에 대해서 생각해보자. 이 문제에서는 로봇이 회전 가능하므로 같은 좌표에 로봇이 있을 수 있는 방법이 2가지(가로방향, 세로방향)가 있다. 따라서 int visited[2][101][101]로 선언하여 방향에 따라 값을 갱신해주어 해결하였다.

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int visited[2][101][101];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

// dir : 0 가로, dir : 1 세로
struct drone {
    int x, y, dir;
};

// 회전시킬 수 있는지 확인
bool canRotate(vector<vector<int>>& board, int x, int y) {
    // 지도를 벗어나면 회전이 불가능
    if (x < 0 || x + 1 > n - 1 || y < 0 || y + 1 > n - 1) return false;
    // 2x2 크기의 정사각형 중에서 한 칸이라도 0이 아니면 회전 불가능
    if (board[y][x] != 0 || board[y][x + 1] != 0 || board[y + 1][x] != 0 || board[y + 1][x + 1] != 0) return false;
    return true;
}

int bfs(vector<vector<int>>& board) {
    n = board.size();
    queue<drone> q;
    q.push({ 0, 0, 0 });
    // 시작점 1로 체크
    visited[0][0][0] = 1;

    while (!q.empty()) {
        drone cur = q.front();
        q.pop();
        int x = cur.x;
        int y = cur.y;
        int dir = cur.dir;

        // 목적지에 도착한 경우
        // 처음 시작점을 1로 시작했으므로 도착점은 1을 빼서 리턴한다.
        if (dir == 0 && x + 1 == n - 1 && y == n - 1) return visited[dir][y][x] - 1;
        if (dir == 1 && x == n - 1 && y + 1 == n - 1) return visited[dir][y][x] - 1;

        // 회전 없이 상하좌우 이동하는 경우
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (dir == 0 && (nx < 0 || nx + 1 > n - 1 || ny < 0 || ny > n - 1)) continue;
            if (dir == 1 && (nx < 0 || nx > n - 1 || ny < 0 || ny + 1 > n - 1)) continue;
            // 로봇이 가로방향이고 이동 가능한 경우
            if (dir == 0 && visited[dir][ny][nx] == 0 && board[ny][nx] == 0 && board[ny][nx + 1] == 0) {
                // 이전 좌표의 이동 횟수 + 1로 갱신
                visited[dir][ny][nx] = visited[dir][y][x] + 1;
                q.push({ nx, ny, dir });
            }
            // 로봇이 세로방향이고 이동 가능한 경우
            if (dir == 1 && visited[dir][ny][nx] == 0 && board[ny][nx] == 0 && board[ny + 1][nx] == 0) {
                visited[dir][ny][nx] = visited[dir][y][x] + 1;
                q.push({ nx, ny, dir });
            }
        }

        // 가로방향일 때 회전하는 경우
        if (dir == 0) {
            // 왼쪽 점을 축으로 위 방향 회전
            if (canRotate(board, x, y - 1) && visited[!dir][y - 1][x] == 0) {
                q.push({ x, y - 1, !dir });
                visited[!dir][y - 1][x] = visited[dir][y][x] + 1;
            }
            // 왼쪽 점을 축으로 아래 방향 회전
            if (canRotate(board, x, y) && visited[!dir][y][x] == 0) {
                q.push({ x, y, !dir });
                visited[!dir][y][x] = visited[dir][y][x] + 1;
            }
            // 오른쪽 점을 축으로 위 방향 회전
            if (canRotate(board, x, y - 1) && visited[!dir][y - 1][x + 1] == 0) {
                q.push({ x + 1, y - 1, !dir });
                visited[!dir][y - 1][x + 1] = visited[dir][y][x] + 1;
            }
            // 오른쪽 점을 축으로 아래 방향 회전
            if (canRotate(board, x, y) && visited[!dir][y][x + 1] == 0) {
                q.push({ x + 1, y, !dir });
                visited[!dir][y][x + 1] = visited[dir][y][x] + 1;
            }
        }
        // 세로방향일 때 회전하는 경우
        if (dir == 1) {
            // 위쪽 점을 축으로 왼쪽 방향 회전
            if (canRotate(board, x - 1, y) && visited[!dir][y][x - 1] == 0) {
                q.push({ x - 1, y, !dir });
                visited[!dir][y][x - 1] = visited[dir][y][x] + 1;
            }
            // 위쪽 점을 축으로 오른쪽 방향 회전
            if (canRotate(board, x, y) && visited[!dir][y][x] == 0) {
                q.push({ x, y, !dir });
                visited[!dir][y][x] = visited[dir][y][x] + 1;
            }
            // 아래 점을 축으로 왼쪽 방향 회전
            if (canRotate(board, x - 1, y) && visited[!dir][y + 1][x - 1] == 0) {
                q.push({ x - 1, y + 1, !dir });
                visited[!dir][y + 1][x - 1] = visited[dir][y][x] + 1;
            }
            // 아래 점을 축으로 오른쪽 방향 회전
            if (canRotate(board, x, y) && visited[!dir][y + 1][x] == 0) {
                q.push({ x, y + 1, !dir });
                visited[!dir][y + 1][x] = visited[dir][y][x] + 1;
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> board) {
    int answer = bfs(board);
    return answer;
}