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

출처

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

프로그래머스

 

문제

 

길이가 2인 로봇은 왼쪽과 오른쪽 둘중 한 축을 기준으로 위 회전이 가능하다. 이 로봇을 적당히 회전시키거나 상하좌우로 이동시켜 목적지까지 이동하는데 걸린 최단 시간을 구하는 문제이다.

 

풀이

이 문제는 어떠한 공식을 적용해서 직접 움직여 보지 않고 해결하기엔 어려운 문제라고 판단하였다. 따라서, 직접 조건에 따라 움직이며 해답을 구하는 시뮬레이션 문제이며, 최단 시간을 구해야하는 조건이 붙었기에 bfs를 활용하여 해결하였다.

 

먼저, 로봇이 방문한 위치를 저장하기 위해서 visited 배열을 선언해주었다. 이때, 로봇의 두 점을 모두 체크해주어야 하기 때문에 boolean[][][][] 4중 배열을 선언하여 각 점을 저장할 수 있도록 하였다. 

 

이후 bfs를 진행할때, 로봇이 회전하거나 상하좌우로 움직일 수 있는 경우를 모두 List로 받아와 큐에 넣고 탐색을 진행하도록 하였다. 회전을 시킬때는 현재 로봇이 가로로 되어있는지, 세로로 되어있는지를 따져 보고 회전을 시켜주었다.

 

visited[][][][]에 표시를 할때 아래와 같이 두번 체크하는 이유는 , 로봇의 두 점이 거꾸로 뒤집어져 있어도 앞뒤 구별이 없기 때문에 똑같은 경우로 취급하기 위해서 이다. ( [1, 1, 2, 2] 와 [2, 2, 1, 1]은 같은 표현 )

 

사실 bfs로 탐색을 진행하는건 다른 bfs와 크게 다르지 않기 때문에, 로봇이 움직일 수 있는 경우만 잘 받아온다면 크게 어려운 문제는 아니라고 생각된다. 자세한 내용은 코드를 참조하면 금방 이해를 할 수 있을것이다.

 

코드

import java.util.*;
class Solution {
    int len;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    
    public int solution(int[][] board) {
        int[] robot = {0, 0, 0, 1, 0};

        len = board.length;
        boolean[][][][] visited = new boolean[len][len][len][len];
        
        visited[0][0][0][1] = true;
        visited[0][1][0][0] = true;
        Deque<int[]> q = new ArrayDeque<>();
        q.addFirst(robot);
        while (!q.isEmpty()) {
            int[] now = q.pollLast();
            
            int x1 = now[0], y1 = now[1], x2 = now[2], y2 = now[3];
            int cnt = now[4];
            
            if ((x1 == len-1 && y1 == len-1) || (x2 == len-1 && y2 == len-1)) {
                return cnt;
            }
            
            for (int[] arr : getNext(board, now)) {
                if (!visited[arr[0]][arr[1]][arr[2]][arr[3]]) {
                    visited[arr[0]][arr[1]][arr[2]][arr[3]] = visited[arr[2]][arr[3]][arr[0]][arr[1]] = true;
                    q.addFirst(new int[]{arr[0], arr[1], arr[2], arr[3], arr[4]});
                }
            }
            
        }
        return -1;
    }
    
    
    public List<int[]> getNext(int[][] board, int[] now) {
        int x1 = now[0], y1 = now[1], x2 = now[2], y2 = now[3];
        int cnt = now[4];
        int d = 0;
        List<int[]> list = new ArrayList<>();
        
        if (y1 == y2) d = 1;
        
        for (int i = 0; i < 4; i++) {
            int nx1 = now[0] + dx[i], ny1 = now[1] + dy[i], nx2 = now[2] + dx[i], ny2 = now[3] + dy[i];
            if (isRange(board, nx1, ny1) && isRange(board, nx2, ny2)) {
                list.add(new int[]{nx1, ny1, nx2, ny2, cnt+1});
            }
        }
        if (d == 0) {
            if (isRange(board, x1+1, y1) && isRange(board, x2+1, y2)) {
                list.add(new int[]{x1, y1, x1+1, y1, cnt+1});
                list.add(new int[]{x2 + 1, y2, x2, y2, cnt+1});
            }
            if (isRange(board, x1-1, y1) && isRange(board, x2-1, y2)) {
                list.add(new int[]{x1, y1, x1-1, y1, cnt+1});
                list.add(new int[]{x2-1, y2, x2, y2, cnt+1});
            }
        } else {
            if (isRange(board, x1, y1+1) && isRange(board, x2, y2+1)) {
                list.add(new int[]{x1, y1, x1, y1 + 1, cnt+1});
                list.add(new int[]{x2, y2 + 1, x2, y2, cnt+1});
            }
            if (isRange(board, x1, y1-1) && isRange(board, x2, y2-1)) {
                list.add(new int[]{x1, y1, x1, y1-1, cnt+1});
                list.add(new int[]{x2, y2 - 1, x2, y2, cnt+1});
            }
        }
        return list;
    }
    
    
    public boolean isRange(int[][] board, int x, int y) {
        return x >= 0 && x < len && y >=0 && y < len && board[x][y] != 1;
    }
}