[Programmers] 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

[Programmers] 블록 이동하기(2020 KAKAO BLIND RECRUITMENT) JAVA

문제 : 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

문제 설명

1*2 크기의 드론(2*1로 회전이 가능하다.)이 지도에서 막히지 않은 곳을 통해 움직일 때, n*n 칸(오른쪽 아래 마지막 칸)으로 가는 최소한의 움직임을 출력하는 문제입니다.

드론은 상, 하, 좌, 우로 움직일 수 있고 가로에서 세로로, 세로에서 가로로 회전할 수 있는데, 회전할 때 닿는 지도가 막혀있으면 회전이 안 됩니다.(자세한 건 그림으로 나와있습니다.)

---

Solution

bfs

bfs로 드론이 한 칸씩 움직일 때마다 방문한 거리를 1씩 더해주며 최종 n*n에 닿았을 때 최종 값을 출력하면 됩니다.

다만 단순하게 1*1 크기의 사람이나 사물이 움직이던 기존의 bfs 문제와 다르게 두 칸을 차지하는 드론이라 문제가 더 복잡해집니다.

저는 기존의 int형 방문 배열을 2차원 배열이 아닌, 3차원 배열로 만들었습니다.

vis[드론이 가로면 0, 세로면 1][세로 좌표][가로 좌표]

이때 세로 좌표와 가로 좌표가 가리키는 1*1 크기의 지도는 드론이 가로면 왼쪽 칸, 드론이 세로면 위쪽 칸을 가리키게 함으로써 방문 여부를 구별하게 했습니다.

또 드론이 움직일 수 있을 때의 경우의 수는 여러 가지 시도를 해봤지만,

드론이 가로 일 때 - 상, 하, 좌, 우로 움직이거나, 위로 회전 2가지, 아래로 회전 2가지

드론이 세로 일 때 - 상, 하, 좌, 우로 움직이거나, 위로 회전 2가지, 아래로 회전 2가지

로 총 16가지의 if 문을 만들어 queue에 담는 식으로 문제를 해결했습니다.

---

Description

• vis 배열에 저장하는 방향, 세로 좌표, 가로 좌표의 세 가지 데이터는 Node라는 클래스를 만들어서 구현했습니다.

---

소스코드

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

class Node{
    private int x;
    private int y;
    private int dir;

    public Node(int dir, int x, int y){
        this.x = x;
        this.y = y;
        this.dir = dir;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getDir() {
        return dir;
    }
}

class Solution {

    public static int[][][] vis;
    public static int n;
    public static int inf;
    public static Queue<Node> q = new LinkedList<>();

    public int solution(int[][] board) {
        n = board.length;
        inf = n*n + 1;
        vis = new int[2][n][n];
        for(int i=0; i<2; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<n;k++){
                    vis[i][j][k] = inf;
                }
            }
        }
        q.offer(new Node(0,0,0));
        vis[0][0][0] = 0;
        while (!q.isEmpty()){
            Node node = q.poll();
            int dir = node.getDir();
            int x = node.getX();
            int y = node.getY();
            int nextCnt = vis[dir][x][y] + 1;
            if(dir==0){
                if(y+2<n && board[x][y+2]==0 && vis[0][x][y+1]==inf){
                    vis[0][x][y+1] = nextCnt;
                    q.offer(new Node(0,x,y+1));
                }
                if(y-1>=0 && board[x][y-1]==0 && vis[0][x][y-1]==inf){
                    vis[0][x][y-1] = nextCnt;
                    q.offer(new Node(0,x,y-1));
                }
                if(x+1<n && board[x+1][y]==0 && board[x+1][y+1]==0 && vis[0][x+1][y]==inf){
                    vis[0][x+1][y] = nextCnt;
                    q.offer(new Node(0,x+1,y));
                }
                if(x-1>=0 && board[x-1][y]==0 && board[x-1][y+1]==0 && vis[0][x-1][y]==inf){
                    vis[0][x-1][y] =  nextCnt;
                    q.offer(new Node(0,x-1,y));
                }
                if(x+1<n && board[x+1][y]==0 && board[x+1][y+1]==0 && vis[1][x][y+1]==inf){
                    vis[1][x][y+1] =  nextCnt;
                    q.offer(new Node(1,x,y+1));
                }
                if(x+1<n && board[x+1][y]==0 && board[x+1][y+1]==0 && vis[1][x][y]==inf){
                    vis[1][x][y] =  nextCnt;
                    q.offer(new Node(1,x,y));
                }
                if(x-1>=0 && board[x-1][y]==0 && board[x-1][y+1]==0 && vis[1][x-1][y+1]==inf){
                    vis[1][x-1][y+1] =  nextCnt;
                    q.offer(new Node(1,x-1,y+1));
                }
                if(x-1>=0 && board[x-1][y]==0 && board[x-1][y+1]==0 && vis[1][x-1][y]==inf){
                    vis[1][x-1][y] =  nextCnt;
                    q.offer(new Node(1,x-1,y));
                }
            }
            else{
                if(x+2<n && board[x+2][y]==0 && vis[1][x+1][y]==inf){
                    vis[1][x+1][y] = nextCnt;
                    q.offer(new Node(1,x+1,y));
                }
                if(x-1>=0 && board[x-1][y]==0 && vis[1][x-1][y]==inf){
                    vis[1][x-1][y] = nextCnt;
                    q.offer(new Node(1,x-1,y));
                }
                if(y+1<n && board[x][y+1]==0 && board[x+1][y+1]==0 && vis[1][x][y+1]==inf){
                    vis[1][x][y+1] = nextCnt;
                    q.offer(new Node(1,x,y+1));
                }
                if(y-1>=0 && board[x][y-1]==0 && board[x+1][y-1]==0 && vis[1][x][y-1]==inf){
                    vis[1][x][y-1] = nextCnt;
                    q.offer(new Node(1,x,y-1));
                }
                if(y+1<n && board[x][y+1]==0 && board[x+1][y+1]==0 && vis[0][x][y]==inf){
                    vis[0][x][y] = nextCnt;
                    q.offer(new Node(0,x,y));
                }
                if(y+1<n && board[x][y+1]==0 && board[x+1][y+1]==0 && vis[0][x+1][y]==inf){
                    vis[0][x+1][y] = nextCnt;
                    q.offer(new Node(0,x+1,y));
                }
                if(y-1>=0 && board[x][y-1]==0 && board[x+1][y-1]==0 && vis[0][x][y-1]==inf){
                    vis[0][x][y-1] = nextCnt;
                    q.offer(new Node(0,x,y-1));
                }
                if(y-1>=0 && board[x][y-1]==0 && board[x+1][y-1]==0 && vis[0][x+1][y-1]==inf){
                    vis[0][x+1][y-1] = nextCnt;
                    q.offer(new Node(0,x+1,y-1));
                }
            }
        }


        int answer = Math.min(vis[0][n-1][n-1-1],vis[1][n-1-1][n-1]);
        return answer;
    }
}