로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
board result
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7
문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
- 처음에는 BFS 문제여서 금방 풀 수 있다고 생각했다. 하지만 회전 때문에 조금 복잡해졌다.
- [YJYOON's 님] 블로그에서 로봇이 방향 D로 평행이동이 가능할 경우 방향 D에 대한 2가지 회전 모두 가능하다. 라는 것을 참고하여 회전 가능 여부를 확인했다.
- Robot 클래스를 선언하고 이동가능 좌표를 뽑아내는 메소드를 만들어서 쉽게 접근하였다.
- 각 좌표의 가로 세로마다 동적계획법을 적용하여 효율성을 높였다.
import java.util.*;
class Solution {
class Robot {
public Robot(int time, int x1, int y1, int x2, int y2) {
this.time = time;
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
public int time;
public int x1;
public int y1;
public int x2;
public int y2;
public ArrayList<int[]> getPosListRotate(int[][] board) {
ArrayList<int[]> result = new ArrayList<int[]>();
//수평일때
if(y1 == y2){
//아래로 회전
if(canMove(x1,y1+1,x2,y2+1,board)){
result.add(new int[]{x1,y1, x1, y1+1});
result.add(new int[]{x2,y2, x2, y2+1});
}
//위로 회전
if(canMove(x1,y1-1,x2,y2-1,board)){
result.add(new int[]{x1,y1-1, x1, y1});
result.add(new int[]{x2,y2-1, x2, y2});
}
}
//수직일때
if(x1 == x2){
//왼쪽으로 회전
if(canMove(x1-1,y1,x2-1,y2,board)){
result.add(new int[]{x1-1,y1, x1, y1});
result.add(new int[]{x2-1,y2, x2, y2});
}
//오른쪽으로 회전
if(canMove(x1+1,y1,x2+1,y2,board)){
result.add(new int[]{x1,y1, x1+1, y1});
result.add(new int[]{x2,y2, x2+1, y2});
}
}
return result;
}
public ArrayList<int[]> getPosListMove(int[][] board) {
ArrayList<int[]> result = new ArrayList<int[]>();
if(canMove(x1+1,y1,x2+1,y2,board)) result.add(new int[] {x1+1,y1,x2+1,y2});
if(canMove(x1-1,y1,x2-1,y2,board)) result.add(new int[] {x1-1,y1,x2-1,y2});
if(canMove(x1,y1+1,x2,y2+1,board)) result.add(new int[] {x1,y1+1,x2,y2+1});
if(canMove(x1,y1-1,x2,y2-1,board)) result.add(new int[] {x1,y1-1,x2,y2-1});
return result;
}
public boolean canMove(int x1, int y1,int x2, int y2, int[][] board){
if(x1 < 0 || x2 >= board.length || y1 < 0 || y2 >= board.length) return false;
if(board[y1][x1] == 1 || board[y2][x2] == 1) return false;
return true;
}
}
int[][][] memo;
public int solution(int[][] board) {
memo = new int[board.length][board.length][2];
for(int i=0; i<board.length; i++)
for(int j=0; j<board.length; j++){
memo[i][j][0] = 10001; //가로
memo[i][j][1] = 10001; //세로
}
Queue<Robot> queue = new LinkedList<Robot>();
queue.offer(new Robot(0,0,0,1,0));
while(!queue.isEmpty()){
Robot robot = queue.poll();
//도착
if(robot.x2 == board.length-1 && robot.y2 == board.length-1)
// break;
return robot.time;
//메모이제이션
if(robot.x1 == robot.x2 ) {//세로
if(robot.time >= memo[robot.y1][robot.x1][1])
continue;
else
memo[robot.y1][robot.x1][1] = robot.time;
}
if(robot.y1 == robot.y2){ //가로
if(robot.time >= memo[robot.y1][robot.x1][0])
continue;
else
memo[robot.y1][robot.x1][0] = robot.time;
}
//탐색
for(int[] pos : robot.getPosListMove(board))
queue.add(new Robot(robot.time+1,pos[0],pos[1],pos[2],pos[3]));
for(int[] pos : robot.getPosListRotate(board))
queue.add(new Robot(robot.time+1,pos[0],pos[1],pos[2],pos[3]));
}
return 0;
}
}