[프로그래머스] 카카오 블라인드 리쿠르트 2020 - 블록 이동하기 (Java)

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

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

문제 설명

 

로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

board	result
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]	7

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

---

풀이

까다로운 조건을 가진 bfs 문제였다.

 

Robot이라는 객체를 만들어 데이터를 관리하였는데 Robot이 board에서 차지하는 공간은 두 칸으로, 이동 시 두 칸 모두 고려해야했다. 처음에는 x, y와 tail_x, tail_y로 두 칸에 대한 인덱스 값을 저장하려고 했는데 이렇게 되면 나중에 회전 처리 시 연산이 복잡해진다.

 

이를 해결하기 위해 x, y를 기준으로 tail이 상하좌우 중 하나에 있는 것으로 표시하는 방법(direction)을 택했다 (0이면 오른쪽, 1이면 아래, 2이면 왼쪽, 3이면 위쪽)

 

방문했던 곳을 기록하기 위한 visted 배열을 3차원으로 만들어 1차원에는 x, 2차원에는 y, 3차원에는 direction을 나타내도록 했다.

 

큐에 담길 Robot 객체를 탐색 시에 고려해야 할 조건은 다음과 같다.

1. 형태 그대로 상하좌우 이동

2. x, y를 기준으로 90도 회전(시계, 반시계)

3. tail을 기준으로 90도 회전(시계, 반시계)

 

1번 같은 경우에는 전통적인 bfs 수도 코드를 떠올려서 구현 가능했지만 2, 3번이 조금 까다로웠다.

 

2,3의 경우 시계방향으로 90도 돌린 뒤 가능 여부를 체크하고, 반시계 방향 90도 (시계방향 270도)로 돌린 뒤 가능 여부를 체크해야하는데, 이때 3의 경우는 꼬리가 아닌 x,y 칸을 돌리는 것이기 때문에 별도의 로직이 필요했다.

 

가능 여부는 다음을 체크해야한다.

1. x,y와 tail x,y가 board 범위 안에 있는지

2. visted[x][y][direction] == false (이미 방문한 곳인지 아닌지)

3. 이동하려는 공간이 벽이 아닌지

 

추가로 회전한 경우에는 다음 조건도 체크해줘야 한다.

- 돌면서 지나가는 대각에 위치한 칸에 벽이 없는지

 

대각 칸을 쉽게 처리하기 위해서 x_diagonal, y_diagonal 배열을 이용했다.

 

자세한 설명은 여기 대단하신 분의 블로그를 참고!

 

+) 로직이 복잡해지면서 변수가 많아지다보니 잘못 입력해 값이 안나와서 애를 먹었다. 진짜 코테 때 착각에 늪에 한 번 빠지면 나가리...

코드

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

public class Solution {

    private int[][] map;
    private boolean[][][] visited;
    private int N;
    private int[] x_move = {0, 1, 0, -1};
    private int[] y_move = {1, 0, -1, 0};
    private final int[] x_diagonal = {-1, 1, 1, -1};
    private final int[] y_diagonal = {1, 1, -1, -1};

    public int solution(int[][] board) {
        N = board.length;
        map = board;
        visited = new boolean[N][N][4];

        return bfs(new Robot(0, 0, 0, 0));
    }

    private int bfs(Robot startBot) {
        Queue<Robot> queue = new LinkedList<>();
        queue.offer(startBot);
        visited[startBot.x][startBot.y][startBot.direction] = true;

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

            if (isFinish(robot.x, robot.y) || isFinish(robot.getTailX(), robot.getTailY())) {
                return robot.time;
            }

            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int new_x = robot.x + x_move[i];
                int new_y = robot.y + y_move[i];
                int new_tail_x = robot.getTailX() + x_move[i];
                int new_tail_y = robot.getTailY() + y_move[i];

                if (!isInArea(new_x, new_y) || !isInArea(new_tail_x, new_tail_y)) {
                    continue;
                }

                if (map[new_x][new_y] == 1 || map[new_tail_x][new_tail_y] == 1) {
                    continue;
                }

                if (visited[new_x][new_y][robot.direction]) {
                    continue;
                }

                visited[new_x][new_y][robot.direction] = true;
                queue.offer(new Robot(new_x, new_y, robot.direction, robot.time + 1));
            }


            // x, y 기준
            for (int i = 1; i < 4; i += 2) { // 시계방향 90도는 + 1, 반시계방향 90도는 +3
                int new_direction = (robot.direction + i) % 4;
                int new_tail_x = robot.x + x_move[new_direction];
                int new_tail_y = robot.y + y_move[new_direction];

                int tempDirection = new_direction;
                if (i != 1) {
                    tempDirection = robot.direction;
                }

                int diagonal_x = robot.x + x_diagonal[tempDirection];
                int diagonal_y = robot.y + y_diagonal[tempDirection];

                if (!isInArea(diagonal_x, diagonal_y) || !isInArea(new_tail_x, new_tail_y)) {
                    continue;
                }

                if (map[new_tail_x][new_tail_y] == 1 || map[diagonal_x][diagonal_y] == 1) {
                    continue;
                }

                if (visited[robot.x][robot.y][new_direction]) {
                    continue;
                }

                visited[robot.x][robot.y][new_direction] = true;
                queue.offer(new Robot(robot.x, robot.y, new_direction, robot.time + 1));
            }


            // tail_x, tail_y 기준
            int direction = (robot.direction + 2) % 4;
            for (int i = 1; i < 4; i += 2) {
                int new_direction = (direction + i) % 4;
                int new_x = robot.getTailX() + x_move[new_direction];
                int new_y = robot.getTailY() + y_move[new_direction];

                int tempDirection = new_direction;
                if (i != 1) {
                    tempDirection = direction;
                }

                int diagonal_x = robot.getTailX() + x_diagonal[tempDirection];
                int diagonal_y = robot.getTailY() + y_diagonal[tempDirection];

                new_direction = (new_direction + 2) % 4;
                if (!isInArea(diagonal_x, diagonal_y) || !isInArea(new_x, new_y)) {
                    continue;
                }

                if (map[new_x][new_y] == 1 || map[diagonal_x][diagonal_y] == 1) {
                    continue;
                }

                if (visited[new_x][new_y][new_direction]) {
                    continue;
                }

                visited[new_x][new_y][new_direction] = true;
                queue.offer(new Robot(new_x, new_y, new_direction, robot.time + 1));
            }
        }

        return -1;
    }

    private boolean isInArea(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }

    private boolean isFinish(int x, int y) {
        return x == N - 1 && y == N - 1;
    }

    class Robot {
        int x;
        int y;
        int direction;
        int time;

        public Robot(int x, int y, int direction, int time) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.time = time;
        }

        public int getTailX() {
            return x + x_move[direction];
        }

        public int getTailY() {
            return y + y_move[direction];
        }

        @Override
        public String toString() {
            return "Robot{" +
                    "x=" + x +
                    ", y=" + y +
                    ", direction=" + direction +
                    ", time=" + time +
                    '}';
        }
    }
}