문제
로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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 함수를 완성해주세요.
코드
import java.util.*;
import java.util.stream.*;
class Solution {
public int solution(int[][] board) {
//int[] = x1, y1, x2, y2, 가로(0) or 세로(1), 몇 초
//적은 시간이 지난 순으로
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(o->o[5]));
pq.add(new int[]{0, 0, 0, 1, 0, 0});
//두 칸 중 왼쪽 위 블록이 기준 블록
//기준 블록의 (x, y, 방향)으로 visited 체크
boolean[][][] visited=new boolean[board.length][board.length][2];
int[][] directions=new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while(!pq.isEmpty()){
int[] ptr= pq.poll();
//블록이 n,n에 닿았다면 정답 출력
if(isDone(ptr, board.length))
return ptr[5];
//방문했었다면 continue
if(visited[ptr[0]][ptr[1]][ptr[4]])
continue;
visited[ptr[0]][ptr[1]][ptr[4]]=true;
//모든 방향에 대해서
for(int[] d:directions){
int dx=ptr[0]+d[0];
int dy=ptr[1]+d[1];
//기준 블록이 지도에서 벗어나는지, 방문했는지, 벽이 있는 지 체크
if(dx<0 || dy<0 || dx>=board.length || dy>=board.length || visited[dx][dy][ptr[4]] || board[dx][dy]==1)
continue;
//가로 방향일 때
if(ptr[4]==0){
//두 번째 블록이 갈 수 없다면 continue;
if(dy+1>=board.length || board[dx][dy+1]==1)
continue;
pq.add(new int[]{dx, dy, dx, dy+1, ptr[4], ptr[5]+1});
}
//세로 방향일 때
if(ptr[4]==1){
//두 번째 블록이 갈 수 없다면 continue;
if(dx+1>=board.length || board[dx+1][dy]==1)
continue;
pq.add(new int[]{dx, dy, dx+1, dy, ptr[4], ptr[5]+1});
}
}
//회전할 수 있는 모든 경우를 큐에 삽입
pq.addAll(getAvailableRotation(visited, ptr, board));
}
return -1;
}
//회전할 수 있는 모든 경우를 리턴하는 메서드
public static List<int[]> getAvailableRotation(boolean[][][] visited, int[] robot, int[][] graph){
List<int[]> list=new ArrayList<>();
int x1=robot[0];
int y1=robot[1];
int x2=robot[2];
int y2=robot[3];
int rotate=robot[4];
//방향이 가로라면,
if(rotate==0){
//현재 두 블록의 윗 두 칸이 비어있으면 위로 회전 가능
if(x1-1>=0 && graph[x1-1][y1]==0 && graph[x1-1][y2]==0){
list.add(new int[]{x1-1, y1, x2, y1, 1, robot[5]+1});
list.add(new int[]{x1-1, y2, x2, y2, 1, robot[5]+1});
}
//현재 두 블록의 아래 두 칸이 비어있으면 아래로 회전 가능
if(x1+1<graph.length && graph[x1+1][y1]==0 && graph[x1+1][y2]==0){
list.add(new int[]{x1, y1, x1+1, y1, 1, robot[5]+1});
list.add(new int[]{x1, y2, x1+1, y2, 1, robot[5]+1});
}
}
//방향이 세로라면,
else{
//현재 두 블록의 오른쪽 두 칸이 비어있으면 오른쪽 회전 가능
if(y1+1<graph.length && graph[x1][y1+1]==0 && graph[x2][y1+1]==0){
list.add(new int[]{x1, y1, x1, y1+1, 0, robot[5]+1});
list.add(new int[]{x2, y2, x2, y1+1, 0, robot[5]+1});
}
//현재 두 블록의 왼쪽 두 칸이 비어있으면 왼쪽 회전 가능
if(y1-1>=0 && graph[x1][y1-1]==0 && graph[x2][y1-1]==0){
list.add(new int[]{x1, y1-1, x1, y1, 0, robot[5]+1});
list.add(new int[]{x2, y1-1, x2, y2, 0, robot[5]+1});
}
}
//회전 가능한 경우 중 방문했던 경우를 제외하고 리턴
return list.stream()
.filter(o->!visited[o[0]][o[1]][o[4]])
.collect(Collectors.toList());
}
//도착하는 경우는 무조건 기준 블록이 아닌 두 번째 블록이 (n,n)에 위치할 때
public static boolean isDone(int[] robot, int n){
return robot[2]==n-1 && robot[3]==n-1;
}
}해결 과정
-
로봇이 차지한 두 블록 중 왼쪽 위의 블록을 기준 블록으로 삼고, 3차원 visited를 사용해서 방문 체크를 했다. 같은 방향으로 이동 가능한 경우와 회전할 경우 모두 탐색해서 가장 빠른 시간에 도착할 수 있도록 우선 순위 큐를 사용했다.
-
😁
