[프로그래머스] 블록이동하기 - BFS

문제

---

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

 

 

 

풀이

---

기존의 2차원 배열의 map 에서 최단거리를 찾는 문제와 같지만 다른점이 있다면 로봇이 두칸을 차지하는 것이다.

 

따로 알고리즘 적으로 어려운 것은 없으나 문제 푸는 방식자체가 코드가 길어지고 조건을 생각해야하는 문제다.

 

이런 문제의 경우 BFS를 사용하는 것이 DFS를 사용하는 것보다 대부분 빠르기 때문에 BFS를 사용하였다.

 

회전을 할 때의 조건만 잘 확인하며 문제를 풀었다.

• 가로의 경우

[a.x ,a.y-1]	[b.x, b.y-1]
[a.x, a.y]	[b.x, b.y]
[a.x, a.y+1]	[b.x, b.y+1]

 

• 세로의 경우

[a.x-1, a.y]	[a.x, a.y]	[a.x+1, a.y]
[b.x-1, b.y]	[b.x, b.y]	[b.x+1, b.y]

 

돌리고 싶은 방향에 맞게 해당 칸을 확인하면 된다.

 

기존의 한칸일 경우는 boolean[][] 배열을 하나만 두어 칸을 지나갔는지 아닌지 확인했다.

하지만 이경우는 가로로 두칸인지 세로로 두칸인지를 두가지로 나누어 확인하였다.

boolean[][] row : 가로로 두칸일 때 칸을 지나갔는지 확인

boolean[][] col : 세로로 두칸일 때 칸을 지나갔는지 확인

 

<전체코드>

import java.util.*;

class Solution {   
    
    static int[] dx = { 1, 0, -1, 0};
    static int[] dy = { 0, 1, 0, -1};
    static int size;
    static boolean[][] row;
    static boolean[][] col;
    
    public int solution(int[][] board) {
        int answer = 0;
        size = board.length;
        
        answer = bfs(board);
        return answer;
    }     
    
    public int bfs(int[][] board){
        
        Queue<robot> queue = new LinkedList<robot>();
        row = new boolean[size][size];
        col = new boolean[size][size];
        
        point sa = new point(0, 0);
        point sb = new point(1, 0);
        row[0][0] = true;
        row[0][1] = true;
        
        queue.add(new robot(sa, sb, 0, 0));
        
        while(!queue.isEmpty()){
            robot now = queue.poll();
            
            if(isEnd(now)){
                return now.count;
            }
            
            point a = now.a;
            point b = now.b;       
            
            if(now.direction == 0){
                for(int i = 0 ; i < 4 ; i++){
                    point na = new point(a.x + dx[i], a.y + dy[i]);
                    point nb = new point(b.x + dx[i], b.y + dy[i]);

                    if(!isPossible(board, na, nb)){
                        continue;
                    }
                    
                    if(row[na.y][na.x] && row[nb.y][nb.x] ) { continue; }
                    
                    row[na.y][na.x] = true;
                    row[nb.y][nb.x] = true;
                    queue.add(new robot(na, nb, 0, now.count + 1));
                }
                
                for(int i  = -1 ; i <= 1 ; i += 2){
                    int nax = a.x;
                    int nay = a.y + i;
                    int nbx = b.x;
                    int nby = b.y + i;
                    
                    if(isPossiblePoint(board, new point(nax, nay)) && isPossiblePoint(board, new point(nbx, nby))){
                       
                        if(isPossible(board, new point(nax, nay), new point(a.x, a.y))
                                     && (!col[nay][nax] || !col[a.y][a.x])){
                            point na = new point(nax, nay);
                            point nb = new point(a.x, a.y);
                            
                            col[na.y][na.x] = true;
                            col[nb.y][nb.x] = true;
                            queue.add(new robot(na, nb, 1, now.count + 1));
                        }
                        
                        if(isPossible(board, new point(nbx, nby), new point(b.x, b.y))
                                     && (!col[nby][nbx] || !col[b.y][b.x])){
                            point na = new point(nbx, nby);
                            point nb = new point(b.x, b.y);
                            
                            col[na.y][na.x] = true;
                            col[nb.y][nb.x] = true;
                            queue.add(new robot(na, nb, 1, now.count + 1));
                        }
                    }                    
                }
            }
            else{
                for(int i = 0 ; i < 4 ; i++){
                    point na = new point(a.x + dx[i], a.y + dy[i]);
                    point nb = new point(b.x + dx[i], b.y + dy[i]);

                    if(!isPossible(board, na, nb)){
                        continue;
                    }
                    
                    if(col[na.y][na.x] && col[nb.y][nb.x] ) { continue; }

                    col[na.y][na.x] = true;
                    col[nb.y][nb.x] = true;
                    queue.add(new robot(na, nb, 1, now.count + 1));
                }
                
                for(int i  = -1 ; i <= 1 ; i += 2){
                    int nax = a.x + i;
                    int nay = a.y;
                    int nbx = b.x + i;
                    int nby = b.y;
                    
                    if(isPossiblePoint(board, new point(nax, nay)) && isPossiblePoint(board, new point(nbx, nby))){
                       
                        if(isPossible(board, new point(nax, nay), new point(a.x, a.y))
                                     && (!row[nay][nax] || !row[a.y][a.x])){
                            point na = new point(nax, nay);
                            point nb = new point(a.x, a.y);
                            
                            row[na.y][na.x] = true;
                            row[nb.y][nb.x] = true;
                            queue.add(new robot(na, nb, 0, now.count + 1));
                        }
                        
                        if(isPossible(board, new point(nbx, nby), new point(b.x, b.y))
                                     && (!row[nby][nbx] || !row[b.y][b.x])){
                            point na = new point(nbx, nby);
                            point nb = new point(b.x, b.y);
                            
                            row[na.y][na.x] = true;
                            row[nb.y][nb.x] = true;
                            queue.add(new robot(na, nb, 0, now.count + 1));
                        }
                    }                    
                }
            }           
        }
        
        return -1;
    }
    static boolean isPossiblePoint(int[][] board, point a){
        if(a.x < 0 || a.x >= size || a.y < 0 || a.y >= size){
            return false;
        }
        
        if(board[a.y][a.x] == 1){
            return false;
        }
        
        return true;
    }
    
    static boolean isPossible(int[][] board, point a, point b){
        
        if(!isPossiblePoint(board, a) || !isPossiblePoint(board, b)){
            return false;
        }
                
        return true;
        
    }
    
    static boolean isEnd(robot r){
        
        if(r.a.x == size -1 && r.a.y == size -1){
            return true;
        }
        
        if(r.b.x == size -1 && r.b.y == size - 1){
            return true;
        }
        
        return false;
    }
    
     static class point{
        int x;
        int y;
        
        point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    static class robot{
        
        point a;
        point b;
        int count;
        int direction;
        
        robot(point a, point b, int direction, int count){
            this.a = a;
            this.b = b;
            this.direction = direction;
            this.count = count;
        }
    }
}