[프로그래머스] Lv 3. 블록 이동하기

문제 풀이 방법 

로봇이 (N,N) 위치까지 이동하는데 필요한 최소 시간을 구해야 합니다.

탐색을 하는데 같은 가중치(= 모든 이동이 같은 비용)를 가지면서 최단 거리를 구하는 문제에서 BFS를 사용한다고 생각했습니다.

 

문제는 로봇이 한칸을 차지하는 것이 아닌 2칸을 차지하는 것과 90도로 회전도 가능하다는 점입니다.

로봇은 아래와 같이 생겼습니다.

 

로봇이 이동할 수 있는 경우는 상,하,좌,우 4가지와 90도 회전이 있습니다.

90도 회전은 현재 로봇의 모양이 가로인지 세로인지에 따라 달라집니다.

 

어떻게 달라질까요?

 

먼저, 로봇이 가로 방향으로 놓였을 때, 회전할 수 있는 방향은 다음과 같습니다.

현재 로봇의 위치가 (y1,x1),(y2,x2)인 경우 회전을 하기 위해 확인해야 할 칸은 살구색으로 색칠한 부분 입니다.

살구색으로 색칠한 부분은 (y1 - 1, x1), (y2 - 1, x2), (y1 + 1, x1), (y2 + 1, x2) 입니다.

이 부분이 1이거나 이동할 수 없는 칸인 경우엔 회전을 할 수 없게 됩니다.

 

 

이 부분을 구현한 코드는 아래와 같습니다.

if(y1 == y2) { // 가로
                for(int d = -1; d <= 1; d+=2) { // 위 방향, 아래 방향
                    if(isValid(y1 + d, x1, y2 + d, x2, board, n)) { // 위쪽 or 아래쪽 이동 가능?
                        if(!visited[y1][x1][y1 + d][x1]) { // 회전 
                            queue.add(new Robot(y1, x1, y1 + d, x1, time + 1));
                            visited[y1][x1][y1 + d][x1] = true;
                        }
                        
                        if(!visited[y2][x2][y2 + d][x2]) {
                            queue.add(new Robot(y2, x2, y2 + d, x2, time + 1));
                            visited[y2][x2][y2 + d][x2] = true;
                        }
                    }
                }
                
            }

 

d의 범위를 -1과 1로 해준 이유는 (y1 - 1, x1), (y2 - 1, x2), (y1 + 1, x1), (y2 + 1, x2) 범위를 잘 분류하면,

(y1 + d, x1),(y1 - d, x1), (y2 + d, x2), (y2 - d, x2)로 묶고 d라는 변수에 -1과 1을 넣어서 회전이 가능한지 확인할 수 있습니다.

로봇을 기준으로 위쪽 칸과 아래 쪽 칸을 분리해 주면 for문으로 구현할 수 있습니다.

 

 

로봇이 세로 방향으로 놓였을 때, 회전할 수 있는 방향은 다음과 같습니다.

 

현재 로봇의 위치가 (y1,x1),(y2,x2)인 경우 회전을 하기 위해 확인해야 할 칸은 살구색으로 색칠한 부분 입니다.

살구색으로 색칠한 부분은 (y1, x1 - 1), (y1, x1 + 1), (y2, x2 - 1), (y2, x2 + 1) 입니다.

이 부분이 1이거나 이동할 수 없는 칸인 경우엔 회전을 할 수 없게 됩니다.

 

BFS를 사용하기 때문에, 한 번 방문한 칸은 다시는 방문할 수 없게 해줘야 합니다.

방문 처리할 땐 로봇이 2개의 칸을 차지 하기 때문에, 4차원 배열을 선언해서 방문을 처리해줍니다.

예를 들어, 로봇이 (0,0),(0,1)이라는 칸에 있는 경우 visited[0][0][0][1] = true 이런식으로 각 좌표를 기준으로 방문 처리를 해줍니다.

 

이 부분을 구현한 코드는 아래와 같습니다.

if(x1 == x2) { // 세로
                
                for(int d = -1; d <= 1; d+=2) {
                    if(isValid(y1, x1 + d, y2, x2 + d, board, n)) { // 위쪽 or 아래쪽 이동 가능?
                        if(!visited[y1][x1][y1][x1 + d]) {
                            queue.add(new Robot(y1, x1, y1, x1 + d, time + 1));
                            visited[y1][x1][y1][x1 + d] = true;
                        }
                        
                        if(!visited[y2][x2][y2][x2 + d]) {
                            queue.add(new Robot(y2, x2, y2, x2 + d, time + 1));
                            visited[y2][x2][y2][x2 + d] = true;
                        }
                    }
                }
            }

 

앞서 이야기한 가로일때 구현한 코드와 동일한 원리입니다.

 

풀이 코드

import java.util.*;

class Solution {
    
    private int[] dy = {-1,0,1,0};
    private int[] dx = {0,1,0,-1};
    
    public class Robot {
        int y1;
        int x1;
        int y2;
        int x2;
        int time;
        
        public Robot(int y1, int x1, int y2, int x2, int time) {
            this.y1 = y1;
            this.x1 = x1;
            this.y2 = y2;
            this.x2 = x2;
            this.time = time;
        }
    }
    
    public int solution(int[][] board) {
        int answer = 0;
        
        
        int n = board.length;
        boolean[][][][] visited = new boolean[n][n][n][n];
        Queue<Robot> queue = new LinkedList<>();
        queue.add(new Robot(0,0,0,1,0));
        visited[0][0][0][1] = true;
        
        while(!queue.isEmpty()) {
            Robot curRobot = queue.poll();
            
            int y1 = curRobot.y1;
            int x1 = curRobot.x1;
            int y2 = curRobot.y2;
            int x2 = curRobot.x2;
            int time = curRobot.time;
            
            if((y1 == n - 1 && x1 == n - 1) || (y2 == n - 1) && (x2 == n - 1)) { // 가장 먼저 도달
                return time;
            }
            
            for(int i = 0; i < 4; i++) { // 상하 좌우
                int ny1 = y1 + dy[i];
                int nx1 = x1 + dx[i];
                int ny2 = y2 + dy[i];
                int nx2 = x2 + dx[i];
                if(isValid(ny1,nx1,ny2,nx2,board,n) && !visited[ny1][nx1][ny2][nx2]) {
                    visited[ny1][nx1][ny2][nx2] = true;
                    queue.add(new Robot(ny1, nx1, ny2, nx2, time + 1));
                }
            }
            
            // 회전 (가로, 세로)
            if(y1 == y2) { // 가로
                
                for(int d = -1; d <= 1; d+=2) { // 위 방향, 아래 방향
                    if(isValid(y1 + d, x1, y2 + d, x2, board, n)) { // 위쪽 or 아래쪽 이동 가능?
                        if(!visited[y1][x1][y1 + d][x1]) { // 회전 
                            queue.add(new Robot(y1, x1, y1 + d, x1, time + 1));
                            visited[y1][x1][y1 + d][x1] = true;
                        }
                        
                        if(!visited[y2][x2][y2 + d][x2]) {
                            queue.add(new Robot(y2, x2, y2 + d, x2, time + 1));
                            visited[y2][x2][y2 + d][x2] = true;
                        }
                    }
                }
                
            } else { // 세로
                
                for(int d = -1; d <= 1; d+=2) {
                    if(isValid(y1, x1 + d, y2, x2 + d, board, n)) { // 위쪽 or 아래쪽 이동 가능?
                        if(!visited[y1][x1][y1][x1 + d]) {
                            queue.add(new Robot(y1, x1, y1, x1 + d, time + 1));
                            visited[y1][x1][y1][x1 + d] = true;
                        }
                        
                        if(!visited[y2][x2][y2][x2 + d]) {
                            queue.add(new Robot(y2, x2, y2, x2 + d, time + 1));
                            visited[y2][x2][y2][x2 + d] = true;
                        }
                    }
                }
            }
            
        }
        
        return -1;
    }
    
    private boolean isValid(int ny1, int nx1, int ny2, int nx2, int[][] map, int n) {
       return ny1 >= 0 && ny1 < n && nx1 >= 0 && nx1 < n && ny2 >= 0 && ny2 < n &&  nx2 >= 0 && nx2 < n
           && map[ny1][nx1] == 0 && map[ny2][nx2] == 0;
    }
}

 

if((y1 == n - 1 && x1 == n - 1) || (y2 == n - 1) && (x2 == n - 1)) { // 가장 먼저 도달
                return time;
            }

 

BFS를 사용하기 때문에 제일 먼저 도착지점을 방문한 Robot이 최소 시간만에 도착지점에 방문한 로봇이 됩니다.

 

출력 결과