[pro] 프로그래머스 level3 60063 블록 이동하기 (Java) - BFS, 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

구현이 복잡해진 BFS 문제이다.

(N, N)에 도착하는 최단 거리를 반환하는 문제이기 때문에 BFS를 이용해서 풀었다.

고려해야 하는 점은 visited 배열을 3차원으로 선언하여 방문한 상태가 수직, 수평인 경우를 분리해줘야 한다는 것이다.

또한 회전하는 경우 역시 수직인 상태에서 회전하는 경우와 수평인 상태에서 회전하는 경우로 나누어 q에 넣어주었다. 수직인 상태에서 회전한다면 좌우 옆 2칸이 비어져있어야 회전 가능하고, 수평인 상태에서 회전한다면 상하 2칸씩이 비어져있어야 회전 가능하다. 로봇이 차지하고 있는 2칸 중 어느 좌표를 축으로 하여 회전하느냐에 따라 이동되는 좌표를 잘 넣어줘야 한다.

 

[코드]

 

import java.util.*;

class Solution {
    
    public int solution(int[][] board) {
        int answer = 0;
        Queue<Robot> q = new LinkedList<>();
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};
        
        int len = board.length;
        boolean[][][] visited = new boolean[len][len][2];
        
        q.add(new Robot(new Point(0, 0), new Point(0, 1), 0, 0));
        
        while(!q.isEmpty()){
            Robot ro = q.poll();
            
            //범위를 벗어나는 경우
            if(ro.p1.r<0 || ro.p1.c<0 || ro.p1.r>=len || ro.p1.c>=len || 
            ro.p2.r<0 || ro.p2.c<0 || ro.p2.r>=len || ro.p2.c>=len) continue;
        
            //벽인 경우
            if(board[ro.p1.r][ro.p1.c]==1 || board[ro.p2.r][ro.p2.c]==1) continue;
            
            //이미 방문한 경우
            if(visited[ro.p1.r][ro.p1.c][ro.vertical] && visited[ro.p2.r][ro.p2.c][ro.vertical]) continue;
            
            //종료 조건
            if((ro.p1.r==len-1 && ro.p1.c==len-1) || 
              (ro.p2.r==len-1 && ro.p2.c==len-1)) {
                answer = ro.t;
                break;
            }
            
            visited[ro.p1.r][ro.p1.c][ro.vertical] = true;
            visited[ro.p2.r][ro.p2.c][ro.vertical] = true;

            
            for(int i = 0; i < 4; i++){
                int nr1 = ro.p1.r+dr[i];
                int nr2 = ro.p2.r+dr[i];
                int nc1 = ro.p1.c+dc[i];
                int nc2 = ro.p2.c+dc[i];
        
                q.add(new Robot(new Point(nr1, nc1), new Point(nr2, nc2), ro.t+1, ro.vertical));
            }
            
            //회전시키기
            if(ro.vertical==1){
                //수직인 경우, 좌우 2칸 확인
                if(ro.p1.c-1>=0 && board[ro.p1.r][ro.p1.c-1]==0 && board[ro.p2.r][ro.p2.c-1]==0){
                    q.add(new Robot(new Point(ro.p1.r, ro.p1.c), new Point(ro.p1.r, ro.p2.c-1), ro.t+1, 0));
                    q.add(new Robot(new Point(ro.p2.r, ro.p1.c-1), new Point(ro.p2.r, ro.p2.c), ro.t+1, 0));
                }
                if(ro.p1.c+1<len && board[ro.p1.r][ro.p1.c+1]==0 && board[ro.p2.r][ro.p2.c+1]==0){
                    q.add(new Robot(new Point(ro.p1.r, ro.p1.c), new Point(ro.p1.r, ro.p2.c+1), ro.t+1, 0));
                    q.add(new Robot(new Point(ro.p2.r, ro.p1.c+1), new Point(ro.p2.r, ro.p2.c), ro.t+1, 0));
                }
            }
            else{
                //수평인 경우, 상하 2칸 확인
                if(ro.p1.r-1>=0 && board[ro.p1.r-1][ro.p1.c]==0 && board[ro.p2.r-1][ro.p2.c]==0){
                    q.add(new Robot(new Point(ro.p1.r-1, ro.p2.c), new Point(ro.p2.r, ro.p2.c), ro.t+1, 1));
                    q.add(new Robot(new Point(ro.p1.r, ro.p1.c), new Point(ro.p2.r-1, ro.p1.c), ro.t+1, 1));
                    
                }
                if(ro.p1.r+1<len && board[ro.p1.r+1][ro.p1.c]==0 && board[ro.p2.r+1][ro.p2.c]==0){
                    q.add(new Robot(new Point(ro.p1.r+1, ro.p2.c), new Point(ro.p2.r, ro.p2.c), ro.t+1, 1));   
                    q.add(new Robot(new Point(ro.p1.r, ro.p1.c), new Point(ro.p2.r+1, ro.p1.c), ro.t+1, 1));   
                }
            }
            
        }
 
        return answer;
    }
    
    class Robot{
        Point p1; 
        Point p2;
        int t;
        int vertical;
        Robot(Point p1, Point p2, int t, int vertical){
            this.p1 = p1;
            this.p2 = p2;
            this.t = t;
            this.vertical = vertical;
        }
    }
    
    class Point{
        int r, c;
        Point(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}