[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 (Java)

프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 : https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기 | 프로그래머스

 

 

구현하는 데 상당히 오랜 시간이 걸린 2020 카카오 공채 마지막 문제 블록 이동하기다.

평소에 bfs를 활용하여 map에서 이동하는 문제를 많이 풀어봐서 금방 풀 줄 알았지만, 회전하는 부분이 까다로워서 오래 걸렸다.

 

처음에는 로봇의 왼쪽 좌표, 오른쪽 좌표를 둘 다 클래스에 저장하여 조작을 했는데, 테스트 케이스 1번만 통과를 하지 못했다.

도저히 어디서 잘못됐는지 모르겠어서 해설을 봤고, (r, c, d)처럼 좌표 하나와 방향을 변수로 가지고 있으라는 것을 보게 되었다.

로봇의 왼쪽, 오른쪽 좌표를 둘 다 가지고 있으면 회전할 때 너무 복잡해지고 체크해야 할 부분도 많아진다.

따라서 해설의 내용대로 전면 수정을 하게 되었다.

 

Robot 클래스는 좌표 x, y와 방향 dir, 시간 time을 가지고 있다.

로봇이 상하좌우로 움직일 때는 x, y와 또 다른 위치인 ox, oy를 상하좌우로 움직여주기만 하면 된다.

문제는 90도 회전을 하는 경우다.

회전은 x, y를 기준으로 회전을 하는 경우와 ox, oy를 기준으로 회전을 하는 경우로 나누었다.

회전할 때 한 가지 고려해야 할 점이 회전하는 방향에는 벽이 없어야 한다는 것이다.

따라서 아래의 사진처럼 좌표를 기준으로 대각선 방향에 있는 위치를 0, 1, 2, 3 번호를 매겨서 rdx, rdy 배열을 선언했다.

 

좌표에 rdx[i], rdy[i]를 더하면 대각선 방향의 위치 좌표가 나오게 된다.

 

예를 들어, 로봇의 현재 방향(dir)이 0이고, 시계방향으로 90도 회전한다고 하면

다음 방향(ndir)은 1이 되고 체크해줘야 할 벽의 위치 인덱스는 1이 된다.

반대로 현재 방향이 0이고, 반시계 방향으로 90도 회전한다고 하면 ndir은 3이 되고 체크해줘야 할 벽의 위치 인덱스는 0이 된다.

따라서 시계방향으로 회전하면 현재 방향(dir)으로 벽을 체크하고, 반시계 방향으로 회전하면 다음 방향(ndir)으로 벽을 체크한다.

나머지는 bfs로 시간이 작은 로봇부터 탐색하며 진행하면 된다.

 

2020 카카오 공채 문제 풀이가 끝났다.

총 7개의 문제 중에 가사 검색, 외벽 점검, 블록 이동하기는 내 힘으로 풀지 못했다.

실제 시험이었다면 시간의 압박 때문에 더 풀지 못하고 떨어졌을 것이다.

어려운 문제도 많이 풀어보고, 좀 더 효율적으로 풀 수 있는 방법이 없을까 고민을 해봐야겠다.

 

 

 

총 걸린 시간 : 3시간 이상

난이도 : ★★★★★

 

코드

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

class Solution {
    private int n;
    private int[][] board;
    private final int[] dx = {0, 1, 0, -1};
    private final int[] dy = {1, 0, -1, 0};
    private final int[] rdx = {-1, 1, 1, -1};
    private final int[] rdy = {1, 1, -1, -1};

    public int solution(int[][] board) {
        this.board = board;
        this.n = board.length;

        Queue<Robot> queue = new LinkedList<>();
        queue.add(new Robot(0, 0, 0, 0)); // 초기 로봇 위치
        boolean[][][] visit = new boolean[n][n][4];
        visit[0][0][0] = true;

        return bfs(queue, visit);
    }

    private int bfs(Queue<Robot> queue, boolean[][][] visit) {
        int x, y, dir, time, ox, oy; // Queue에서 꺼낸 로봇의 x, y, 방향, 시간, 다른 x, y
        int nx, ny, nox, noy, ndir; // 로봇이 이동 후 가지게 되는 위치 및 방향 (nox : next other x)
        int rx, ry; // 회전할 때 판단해야 할 벽의 위치

        while (!queue.isEmpty()) {
            Robot robot = queue.poll();
            x = robot.x;
            y = robot.y;
            dir = robot.dir;
            time = robot.time;
            ox = robot.getOtherX();
            oy = robot.getOtherY();

            if (isFinish(x, y) || isFinish(ox, oy)) return time; // 도착하면 리턴

            for (int i = 0; i < 4; i++) { // 상하좌우 이동
                nx = x + dx[i];
                ny = y + dy[i];
                nox = ox + dx[i];
                noy = oy + dy[i];

                if (!isValid(nx, ny) || !isValid(nox, noy)) continue; // 벽 밖으로 나갔는지 체크
                if (board[nx][ny] == 1 || board[nox][noy] == 1) continue; // 벽인지 체크
                if (visit[nx][ny][dir]) continue; // 이미 방문한 곳인지 체크

                visit[nx][ny][dir] = true;
                queue.add(new Robot(nx, ny, dir, time + 1));
            }

            for (int i = 1; i < 4; i += 2) { // x, y를 기준으로 90도 회전
                ndir = (dir + i) % 4;
                nox = x + dx[ndir];
                noy = y + dy[ndir];

                int tempDir = (i == 1) ? ndir : dir;
                rx = x + rdx[tempDir];
                ry = y + rdy[tempDir];

                if (!isValid(nox, noy) || !isValid(rx, ry)) continue;
                if (board[nox][noy] == 1 || board[rx][ry] == 1) continue;
                if (visit[x][y][ndir]) continue;

                visit[x][y][ndir] = true;
                queue.add(new Robot(x, y, ndir, time + 1));
            }

            dir = (dir + 2) % 4; // 방향 반대 처리
            for (int i = 1; i < 4; i += 2) { // ox, oy를 기준으로 90도 회전
                ndir = (dir + i) % 4;
                nx = ox + dx[ndir];
                ny = oy + dy[ndir];

                int tempDir = (i == 1) ? ndir : dir;
                rx = ox + rdx[tempDir];
                ry = oy + rdy[tempDir];

                ndir = (ndir + 2) % 4;
                if (!isValid(nx, ny) || !isValid(rx, ry)) continue;
                if (board[nx][ny] == 1 || board[rx][ry] == 1) continue;
                if (visit[nx][ny][ndir]) continue;

                visit[nx][ny][ndir] = true;
                queue.add(new Robot(nx, ny, ndir, time + 1));
            }
        }
        return -1;
    }

    private boolean isValid(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;
    }

    private class Robot {
        int x, y;
        int dir;
        int time;

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

        public int getOtherX() {
            return x + dx[dir];
        }

        public int getOtherY() {
            return y + dy[dir];
        }

        @Override
        public String toString() {
            return "time:" + time + "  (" + x + "," + y + ") (" + getOtherX() + "," + getOtherY() + ") dir:" + dir;
        }
    }
}