블록 이동하기 : https://programmers.co.kr/learn/courses/30/lessons/60063
Problem
Solve
상하좌우와 90도 회전하는 경우를 가지고 BFS를 사용하는 문제.
짜잘한 조건이 많아서 그것 때문에 시간이 오래걸렸다..
회전을 했을 경우 위의 그림과 같이 기준 축을 중심으로 90도 회전하게 되는데 회전하는 축이 이동하는 좌표에 1이 존재한다면 회전할수 없다.
이를 참고하고 'ㅡ'상태인 경우 'ㅣ'로 회전하는 경우가 4가지, 'ㅣ'상태에서 'ㅡ'로 회전하는 경우가 4가지가 있다.
그리고 회전할수 있는 조건을 따지면
'ㅡ'상태를 'ㅣ'로 회전할때 왼쪽 좌표를 위로 회전시키는 경우 회전 좌표가 (i,j)일때 (i-1,j)와 (i-1, j+1)의 좌표가 0이어야한다.
마찬가지로 'ㅡ'상태를 'ㅣ'로 회전할 때 왼쪽 좌표를 아래로 회전시키는 경우 회전 좌표가 (i,j)일 때 (i+1,j)와 (i+1,j+1)이 0이어야한다.
'ㅣ'상태를 'ㅡ'로 회전할 때 위쪽 좌표를 오른쪽으로 회전시키는 경우 회전 좌표가 (i,j)일 때 (i,j+1)과 (i+1, j+1)이 0이어야한다.
(사진에 i-1으로 되어있는데 i+1이어야한다.)
그 다음은 저장 좌표의 위치이다.
나는 좌표를 저장하는 인스턴스에 y1,x1,y2,x2로만 선언해놓았고, 임의로 'ㅡ'상태일때는 y1,x1이 왼쪽 좌표, y2,x2가 오른쪽 좌표, 그리고 'ㅣ'상태일때는 y1,x2이 위쪽 좌표, y2,x2가 아래 좌표로 생각하고 회전시 좌표값들을 갱신하였다.
복잡하니 코드를 보고 이해하면 될듯하다.
그리고 각 상태의 방문여부를 확인해야하므로 visit[y][x][state]로 3차배열을 사용해서 중복되는 방문을 방지한다.
Code
import java.util.*;
class Solution {
int[] dy = {-1,0,1,0};
int[] dx = {0,-1,0,1};
int answer=0;
public int solution(int[][] board) {
return move(board);
}
int move(int[][] board){
Queue<Robot> queue = new LinkedList<>();
queue.offer(new Robot(0,0,0,1,0,0));
int N = board.length;
boolean[][][] visit = new boolean[N][N][2];
while(!queue.isEmpty()){
Robot robot = queue.poll();
int time = robot.time;
int state = robot.state;
int y1 = robot.y1;
int x1 = robot.x1;
int y2 = robot.y2;
int x2 = robot.x2;
if(visit[y1][x1][state] && visit[y2][x2][state]) continue;
//어떤 상태이든지 두 좌표중 하나만이라도 board의 끝 좌표에 도달하면 해당 시간 반환.
if(y1==N-1&&x1==N-1 || y2==N-1&&x2==N-1) return time;
visit[y1][x1][state] = true;
visit[y2][x2][state] = true;
//상하좌우
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];
int nstate = state;
if(checkRange(ny1,nx1,board) && checkRange(ny2,nx2,board)){
queue.add(new Robot(ny1,nx1,ny2,nx2,time+1,state));
}
}
//회전
//세로상태('ㅣ')일때는 위가 y1,x1, 아래가 y2,x2
//가로상태('ㅡ')일때는 왼쪽이 y1,x1, 오른쪽이 y2,x2
//'ㅡ'상태에서 왼쪽 좌표가 위쪽으로 회전하는 경우
//왼쪽좌표가 위쪽으로 이동하니 queue에 저장할때 y1,x1과 y2,x2를 그 자리 그대로 넣어준다.
if(state==0 && checkRange(y1+1,x1,board)&&checkRange(y1+1,x1+1,board)){
queue.add(new Robot(y2,x2,y1+1,x1+1,time+1,1));
}
//'ㅡ'상태에서 오른쪽 좌표가 위쪽으로 회전하는 경우
//오른쪽 좌표가 위쪽으로 이동하니 y1,x1과 y2,x2의 자리를 교차해서 queue에 저장
if(state== 0&&checkRange(y2+1,x2,board)&&checkRange(y2+1,x2-1,board)){
queue.add(new Robot(y1,x1,y2+1,x2-1,time+1,1));
}
//'ㅡ'상태에서 왼쪽좌표가 아래로 회전하는 경우
//왼쪽에서 아래이므로 y1,x1과 y2,x2의 위치가 변경되서 저장되어야한다.
if(state==0&&checkRange(y1-1,x1,board)&&checkRange(y1-1,x1+1,board)){
queue.add(new Robot(y1-1,x1+1,y2,x2,time+1,1));
}
//'ㅡ'상태에서 오른쪽좌표가 아래로 회전하는 경우
//오른쪽에서 아래이므로 각 좌표의 위치는 변경되지 않는다.
if(state==0&&checkRange(y2-1,x2,board)&&checkRange(y2-1,x2-1,board)){
queue.add(new Robot(y2-1,x2-1,y1,x1,time+1,1));
}
//'ㅣ'상태에서 위쪽좌표가 오른쪽으로 회전하는 경우
//위쪽좌표가 오른쪽으로 회전하므로 각 좌표의 위치를 변경해서 저장한다.
if(state==1&&checkRange(y1,x1+1,board)&&checkRange(y1+1,x1+1,board)){
queue.add(new Robot(y2,x2,y1+1,x1+1,time+1,0));
}
//'ㅣ'상태에서 위쪽좌표가 왼쪽으로 회전하는 경우
//각 좌표의 위치 변경X
if(state==1&&checkRange(y1,x1-1,board)&&checkRange(y1+1,x1-1,board)){
queue.add(new Robot(y1+1,x1-1,y2,x2,time+1,0));
}
//'ㅣ'상태에서 아래좌표가 오른쪽으로 회전하는 경우
//각 좌표의 위치 변경 X
if(state==1&&checkRange(y2,x2+1,board)&&checkRange(y2-1,x2+1,board)){
queue.add(new Robot(y1,x1,y2-1,x2+1,time+1,0));
}
//'ㅣ'상태에서 아래좌표가 왼쪽으로 회전하는 경우
//각 좌표의 위치 변경
if(state==1&&checkRange(y2,x2-1,board)&&checkRange(y2-1,x2-1,board)){
queue.add(new Robot(y2-1,x2-1,y1,x1,time+1,0));
}
}
return 0;
}
//해당 좌표가 범위를 벗어나는지 좌표의 값이 0인지 판단
boolean checkRange(int y, int x, int[][] board){
int N = board.length;
if(y>=0 && x>=0 && y<N && x<N && board[y][x]==0) return true;
return false;
}
class Robot{
int y1;
int x1;
int y2;
int x2;
int time;
int state;
public Robot(int y1, int x1, int y2, int x2, int time, int state){
this.y1=y1;
this.x1=x1;
this.y2=y2;
this.x2=x2;
this.time=time;
this.state=state;
}
}
}Result
Reference
