[프로그래머스/자바] 블록 이동하기 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

BFS로 최단 거리를 찾는 문제와 동일한 형태다.

다만 회전하는 케이스가 다양해서 구현하는게 좀 복잡하다.

 

로봇이 가로로 있을 때는 차지하는 두칸 중 왼쪽 칸을 기준으로, 

세로로 있을 때는 차지하는 두칸 중 위쪽 칸을 기준으로 보고 

visit를 확인하고 변경해줄 때도 기준이 되는 칸만 검사했다.

똑같은 칸을 지나가더라도 가로로 지나갈 때와 세로로 지나갈 때는 다르므로

visit를 3차원 배열로 만들어 가로, 세로 방문 체크를 따로했다. (visit[방향][행][열])

 

q에 있는 값을 하나씩 꺼내면서 

상하좌우로 이동하는 move 배열의 값을 더해 이동시켰고,

회전할 때는 hRotate와 vRotate 배열의 값을 더해 회전시켰다.

 

hRotate 배열의 값을 회전시킬 때 벽인지 아닌지 확인해야 할 칸을 hCheck에 담았고,

hCheck의 값이 1이 아닌 경우에만 회전시킬 수 있도록 했다.

 

 

예를 들어 현재 큐에서 꺼낸 Robot의 위치가 3, 4고 방향은 가로일 때

회전하기 위해 hRotate 배열의 값을 하나하나 더해야 한다.

처음으로 hRotate[0]의 값 {-1, 0}을 더하면 2, 4 위치의 세로 로봇이 된다.

이때 hCheck[0]의 값 {-1, 1}을 더한 2, 5 위치의 칸이 벽인지 검사해야 한다.

 

hRotate, hCheck, vRotate, vCheck를 생성해

회전하는 8가지 경우 모두를 고려했다.

 

회전하는 경우, 이동하는 경우 모두 

check() 메소드를 통해 nextX, nextY가 배열의 인덱스에 벗어나지 않고, 방문한 적이 없고, 벽이 아닌지를 체크한다.

 

 

배운점 및 느낀점

방향별로 나누어서 방문체크를 하거나 값을 저장한다는 점에서

2020 카카오 인턴십의 경주로 건설과 비슷하다고 느꼈다.

경주로 건설을 풀어봤기 때문에 방향별로 3차원 배열의 visit를 만드는 건 바로 생각해낼 수 있었다.

 

다만 회전하는 부분을 어떻게 처리할지가 좀 어려워서 배열로 일일이 다 구현했다.

모든 경우를 배열로 적은 점이 비효율적이지 않았나 싶다.

다른분들 코드를 참고해서 코드를 수정해봐야겠다.

 

 

import java.util.*;

class Solution {
    // 상하좌우 이동
    static int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 가로 -> 세로 회전 (↖ ↙ ↗ ↘ 순서)
    static int[][] hRotate = {{-1, 0}, {0, 0}, {-1, 1}, {0, 1}};
    static int[][] hCheck = {{-1, 1}, {1, 1}, {-1, 0}, {1, 0}};
    // 세로 -> 가로 회전 (↖ ↙ ↗ ↘ 순서)
    static int[][] vRotate = {{0, -1}, {1, -1}, {0, 0}, {1, 0}};
    static int[][] vCheck = {{1, -1}, {0, -1}, {1, 1}, {0, 1}};

    static int[][] newBoard;
    static int ans = 0;
    static boolean[][][] visit;
    static int n;

    static class Robot {
        int x, y, dir, sec;

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

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

        // 0: 가로, 1: 세로
        visit = new boolean[2][n][n];

        BFS();
        return ans;
    }

    static void BFS() {
        Queue<Robot> q = new LinkedList<>();

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

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

            if((now.dir == 0 && now.x == n - 1 && now.y + 1 == n - 1) || 
                    (now.dir == 1 && now.x + 1 == n - 1 && now.y == n - 1)) {
                ans = now.sec;
                break;
            }

            // 상하좌우 이동
            for(int i=0;i<4;i++) {
                int nextX = now.x + move[i][0];
                int nextY = now.y + move[i][1];

                if(check(nextX, nextY, now.dir)) {
                    visit[now.dir][nextX][nextY] = true;
                    q.offer(new Robot(nextX, nextY, now.dir, now.sec + 1));
                }
            }

            if(now.dir == 0) { // 가로 -> 세로 회전
                for(int i=0;i<4;i++) {
                    int nextX = now.x + hRocate[i][0];
                    int nextY = now.y + hRocate[i][1];
                    int nextDir = 1;

                    if(check(nextX, nextY, nextDir) && newBoard[now.x + hCheck[i][0]][now.y + hCheck[i][1]] == 0) {
                        visit[nextDir][nextX][nextY] = true;
                        q.offer(new Robot(nextX, nextY, nextDir, now.sec + 1));
                    }
                }
            }
            else { // 세로 -> 가로 회전
                for(int i=0;i<4;i++) {
                    int nextX = now.x + vRocate[i][0];
                    int nextY = now.y + vRocate[i][1];
                    int nextDir = 0;

                    if(check(nextX, nextY, nextDir) && newBoard[now.x + vCheck[i][0]][now.y + vCheck[i][1]] == 0) {
                        visit[nextDir][nextX][nextY] = true;
                        q.offer(new Robot(nextX, nextY, nextDir, now.sec + 1));
                    }
                }
            }
        }
    }

    static boolean check(int x, int y, int dir) {
        // 이미 방문한 경우, 배열 범위 벗어난 경우, 벽인 경우
        if(x < 0 || x >= n || y < 0 || y >= n || visit[dir][x][y] || newBoard[x][y] == 1)
            return false;

        if(dir == 0 && (y + 1 >= n || newBoard[x][y + 1] == 1)) 
            return false;

        if(dir == 1 && (x + 1 >= n || newBoard[x + 1][y] == 1)) 
            return false;

        return true;
    }
}