[카카오 기출 문제]블록 이동하기 - 레벨 3, BFS

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

프로그래머스

 

기억해야할점들 

첫번쨰, 행(row)와 열(col)을 잘 확인합니다.

문제를 잘읽어야합니다. 

 

두번쨰, 로봇 회전시에 회전조건입니다.

로봇이 회전할떄 회전하는 방향에 벽이 없어야합니다. 로봇이 아래쪽으로 회전한다고하면 

아래 두개에 벽이 둘다 없어야합니다. 

 

세번째, Row와 Col 방문조건을 각각 사용합니다.

Visited[Board.length][Board.length][2] 로 하여

Visited[][][0] 은 열. (즉 여기서는 col)

Visited[][][1] 은 행. (여기서는 row)

로 구분하여 방문처리를 합니다.

 

또한, 이미 방문했다면 방문하지 않을떄 조건은 두 개의 로봇이 세로모양으로 방문했을때

Visited[][][1] Visited[][][1] 둘중 하나라도 아직 방문한적이 없다면 해당 모양을 아직 방문한적이 없으므로

한개라도 false라면 방문가능합니다.

 

일반적인 BFS이지만, 코딩 시에 조건이 많아 오류가 생길가능성이 많기에

전체적으로 어떻게 진행할지 생각하고 코딩해야 시간이 더 적게 걸립니다.

 

 

 

코드입니다.

import java.util.*;
class Solution {
    int answer = Integer.MAX_VALUE;
    int[][] Board;
    boolean[][][] Visited;
    
    public int solution(int[][] board) {
        Board = board;
        //[][][0] : COL 방문배열, [][][1] : ROW 방문배열
        Visited = new boolean[Board.length][Board.length][2];
        simulate();
        
        return answer;
    }
    
    void simulate(){
        Queue<Robot> q = new LinkedList<Robot>();
        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};
        //가로면 0 세로면 1
        q.offer(new Robot(0,0,0,1,0,0));
        Visited[0][0][0] = true;
        Visited[0][1][0] = true;
        
        while(!q.isEmpty()){
            Robot temp = q.poll();
            int r1 = temp.r1; int c1 = temp.c1;
            int r2 = temp.r2; int c2 = temp.c2;
            int shape = temp.shape;
            
            if( (r1 == Board.length -1 && c1 == Board.length - 1) || (r2 == Board.length -1 && c2 == Board.length - 1) ){
                answer = Math.min(answer, temp.time);
                return; 
            }
            
            for(int direction=0;direction<4;direction++){
                int nr1 = r1 + dx[direction]; int nc1 = c1 + dy[direction];
                int nr2 = r2 + dx[direction]; int nc2 = c2 + dy[direction];
                // System.out.println("r1:"+r1 +" c1:"+c1 +" r2: "+r2+" c2:"+c2);
                if(nr1 < 0 || nr1 >= Board.length || nc1 < 0 || nc1 >= Board.length || Board[nr1][nc1] == 1) continue;
                if(nr2 < 0 || nr2 >= Board.length || nc2 < 0 || nc2 >= Board.length || Board[nr2][nc2] == 1) continue;
                if(Visited[nr1][nc1][shape] == true && Visited[nr2][nc2][shape] == true) continue;
                Visited[nr1][nc1][shape] = true;
                Visited[nr2][nc2][shape] = true;
                q.offer(new Robot(nr1, nc1, nr2, nc2, shape, temp.time + 1));
            }
            // System.out.println("r1:"+r1 +" c1:"+c1 +" r2: "+r2+" c2:"+c2);
            //가로모양이라면
            if(temp.shape == 0){
                //가로이면서 아래로 회전할 수 있는지 체크
                if( (r1+1 < Board.length && Board[r1+1][c1] == 0) && ( r2+1 < Board.length && Board[r2+1][c2] == 0 ) ){
                    //1번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r1][c1][1] == false || Visited[r1+1][c1][1] == false){
                        Visited[r1][c1][1] = true;
                        Visited[r1+1][c1][1] = true;
                        q.offer(new Robot(r1, c1, r1+1, c1, 1, temp.time + 1));
                    }
                    //2번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r2+1][c2][1] == false || Visited[r2][c2][1] == false){
                        Visited[r2+1][c2][1] = true;
                        Visited[r2][c2][1] = true;
                        q.offer(new Robot(r2+1, c2, r2, c2, 1, temp.time + 1));
                    }
                    
                }
                //가로이면서 위로 회전할 수 있는지 체크
                if( (r1-1 >= 0 && Board[r1-1][c1] == 0) && ( r2-1 >= 0 && Board[r2-1][c2] == 0 ) ){
                    //1번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r1][c1][1] == false || Visited[r1-1][c1][1] == false){
                        Visited[r1][c1][1] = true;
                        Visited[r1-1][c1][1] = true;
                        q.offer(new Robot(r1, c1, r1-1, c1, 1, temp.time + 1));
                    }
                    //2번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r2-1][c2][1] == false || Visited[r2][c2][1] == false){
                        Visited[r2-1][c2][1] = true;
                        Visited[r2][c2][1] = true;
                        q.offer(new Robot(r2-1, c2, r2, c2, 1, temp.time + 1));
                    }
                    
                }
            }
            //세로일떄
            if(temp.shape == 1){
                
                //세로이면서 왼쪽로 회전할 수 있는지 체크
                if( (c1-1 >= 0 && Board[r1][c1-1] == 0) && ( c2-1 >= 0 && Board[r2][c2-1] == 0 ) ){
                    //1번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 가로모양으로는 방문안한것임.
                    if(Visited[r1][c1][0] == false || Visited[r1][c1-1][0] == false){
                        Visited[r1][c1][0] = true;
                        Visited[r1][c1-1][0] = true;
                        q.offer(new Robot(r1, c1, r1, c1-1, 0, temp.time + 1));
                    }
                    //2번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r2][c2-1][0] == false || Visited[r2][c2][0] == false){
                        Visited[r2][c2-1][0] = true;
                        Visited[r2][c2][0] = true;
                        q.offer(new Robot(r2, c2-1, r2, c2, 0, temp.time + 1));
                    }
                }
                
                
                //세로이면서 오른쪽으로 회전할 수 있는지 체크
                if( (c1+1 < Board.length && Board[r1][c1+1] == 0) && ( c2+1 < Board.length && Board[r2][c2+1] == 0 ) ){
                    //1번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r1][c1][0] == false || Visited[r1][c1+1][0] == false){
                        Visited[r1][c1][0] = true;
                        Visited[r1][c1+1][0] = true;
                        q.offer(new Robot(r1, c1, r1, c1+1, 0, temp.time + 1));
                    }
                    //2번로봇이 회전축일때, 한개라도 방문하지 않은적이 있다면 아직 세로모양으로는 방문안한것임.
                    if(Visited[r2][c2+1][0] == false || Visited[r2][c2][0] == false){
                        Visited[r2][c2+1][0] = true;
                        Visited[r2][c2][0] = true;
                        q.offer(new Robot(r2, c2+1, r2, c2, 0, temp.time + 1));
                    }
                    
                }
                
            }
            
            
            
        }
        
    }
    
    class Robot{
        int r1; int c1;
        int r2; int c2;
        int shape;
        int time;
        Robot(int r1, int c1, int r2, int c2, int shape, int time){
            this.r1 = r1;
            this.c1 = c1;
            this.r2 = r2;
            this.c2 = c2;
            this.shape = shape;
            this.time = time;
        }
    }
}