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

문제

 

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

 

 

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

 

 

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

 

---

풀이

 

2020 KAKAO BLIND RECRUITMENT 문제다. 풀고 나면 그렇게 어려운 문제가 아니었는데, 계속 한 군데씩 문제가 생겨서 오래걸렸던 문제이다. 로봇이 회전하는 부분의 아이디가 떠오르지 않아서 카카오 기술 블로그를 참고했다.

• (r, c, d) : (r, c) 위치에서 d 방향에 있는 칸을 한 칸 더 차지하고 있음

(r, c)를 기준으로 로봇의 방향에 따라 (r, c + 1), (r + 1, c), (r, c - 1), (r - 1, c)도 추가로 저장해서 기준이 한 칸 더 있음을 명시 해줬다.

 

이 상태에서 로봇은 총 8가지의 방법으로 움직인다.

• 로봇이 상, 하, 좌, 우로 움직임(4가지)
• 로봇이 첫 번째 칸을 기준으로 시계 방향, 반시계 방향으로 회전(2가지)
• 로봇이 두 번째 칸을 기준으로 시계 방향, 반시계 방향으로 회전(2가지)
• 로봇은 항상 수평 또는 수직으로만 놓이기 때문에, 충돌 확인을 해야하는 후보칸은 회전축을 기준으로 대각선 방향에 있는 칸 4개이다.
• 충돌 확인을 해야하는 칸은 회전하기 전에 로봇이 위치한 칸(축이 아닌 칸)까지의 맨해튼 거리와 회전한 후에 로봇이 새로 위치한 칸까지의 맨해튼 거리가 1이다.
  • 맨해튼 거리 : |x1 - x2| + |y1 - y2|
    
    

위 조건에 맞춰 BFS를 구현하면 되는데, 코드를 설명하면

• visited 배열을 3차원으로 두고 로봇의 네 방향에 따라 방문을 검색한다. 
• 로봇의 첫 번째 칸을 (x, y), 두 번째 칸을 (px, py)라고 할 때
  • (x, y)를 기준으로 회전할 때는 좌표의 변화 없이 방향만 바뀌기 때문에 큐에 넣어 줄 때에도 x, y 좌표와 회전한 방향만 넣어준다.
  • (px, py)를 기준으로 회전할 때는 (x, y) → (nx, ny)를 기준 삼기 위해 방향을 반대로 바꾸고, 큐에 넣을 때도 (px, py)가 아닌 (nx, ny)의 좌표와 방향을 넣어준다.

 

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static final int[] dx = {0, 1, 0, -1};
    public static final int[] dy = {1, 0, -1, 0};
    public static final int[] rx = {-1, 1, 1, -1};
    public static final int[] ry = {1, 1, -1, -1};

    public static Queue<Robot> q = new LinkedList<>();
    public static boolean[][][] visited = new boolean[101][101][4];
    public static int N;

    public static class Robot {
        int x;
        int y;
        int d;
        int move;

        public Robot(int x, int y, int d, int move) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.move = move;
        }
    }

    public static boolean outOfRange(int x, int y, int px, int py) {
        if(x < 0 || x >= N || y < 0 || y >= N) return true;
        return px < 0 || px >= N || py < 0 || py >= N;
    }

    public static int moveStraight(int[][] board, Robot robot) {
        int x = robot.x;
        int y = robot.y;
        int d = robot.d;
        int move = robot.move;

        int px = x + dx[d];
        int py = y + dy[d];

        if((x == N - 1 && y == N - 1)
                || px == N - 1 && py == N - 1) return move;

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int npx = px + dx[i];
            int npy = py + dy[i];

            if(outOfRange(nx, ny, npx, npy)) continue;
            if(board[nx][ny]== 1 || board[npx][npy] == 1 || visited[nx][ny][d]) continue;

            visited[nx][ny][d] = true;
            q.offer(new Robot(nx, ny, d, move + 1));
        }

        return 0;
    }

    public static int moveRotate(int[][] board, Robot robot) {
        int x = robot.x;
        int y = robot.y;
        int d = robot.d;
        int move = robot.move;

        int px = x + dx[d];
        int py = y + dy[d];

        if((x == N - 1 && y == N - 1)
                || px == N - 1 && py == N - 1) return move;

        for(int i=1; i<4; i+=2) {
            int nd = (d + i) % 4;
            int npx = x + dx[nd];
            int npy = y + dy[nd];
            int dir = d;
            int nrx, nry;

            if(i == 1) {
                dir = nd;
            }
            nrx = x + rx[dir];
            nry = y + ry[dir];

            if(outOfRange(npx, npy, nrx, nry)) continue;
            if(board[npx][npy] == 1 || board[nrx][nry] == 1 || visited[x][y][nd]) continue;

            visited[x][y][nd] = true;
            q.offer(new Robot(x, y, nd, move + 1));
        }

        d = (d + 2) % 4;
        for(int i=1; i<4; i+=2) {
            int nd = (d + i) % 4;
            int npx = px + dx[nd];
            int npy = py + dy[nd];
            int dir = d;
            int nrx, nry;

            if(i == 1) {
                dir = nd;
            }
            nrx = px + rx[dir];
            nry = py + ry[dir];
            nd = (nd + 2) % 4;

            if(outOfRange(npx, npy, nrx, nry)) continue;
            if(board[npx][npy] == 1 || board[nrx][nry] == 1 || visited[npx][npy][nd]) continue;

            visited[npx][npy][nd] = true;
            q.offer(new Robot(npx, npy, nd, move + 1));
        }
        return 0;
    }

    public static int bfs(int[][] board) {
        q = new LinkedList<>();
        visited = new boolean[101][101][4];
        N = board.length;
        int ret = 0;

        q.offer(new Robot(0, 0, 0, 0));
        visited[0][0][0] = true;

        while(!q.isEmpty()) {
            Robot robot = q.poll();

            int straight = moveStraight(board, robot);
            if(straight != 0) {
                ret = straight;
                break;
            };

            int rotate = moveRotate(board, robot);
            if(rotate != 0) {
                ret = rotate;
                break;
            }
        }
        return ret;
    }

    public int solution(int[][] board) {
        return bfs(board);
    }
}