[2020 KAKAO BLIND RECRUITMENT] 블록 이동하기(Java, 간단한 코드, DFS? or BFS?)

## 접근

---

1. DFS와 BFS 중 선택, DFS는 구현이 간단하지만 최소 시간을 구할 때는 적합하지 않다. 따라서, Depth(Time)을 확인할 수 있는 BFS를 선택.

 

 

 

2. 방문 표시를 통해서, 재탐색이 이루어지지 않도록 한다.(시간초과방지), 로봇 상태를 구분해서 방문 표시를 해야 하므로 3차원 배열을 사용해야 한다. 2차원 배열 시에, 수직과 수평의 구분이 없어지므로 주의한다.

 

 

 

3. 회전을 한다는 것을, 로봇의 아래, 위, 오른쪽, 왼쪽의 2칸이 모두 비어있어야 함을 의미한다. 코드에서 구현을 확인하도록 한다.

 

 

 

 

## 유의사항

---

1. 변수를 사용할 때, x1, y1, x2, y2는 지양한다. 문자에 숫자를 덧붙여 쓰다보니, 실수를 할 수 있다.

 

 

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
class Solution {
    class Item{
        int x1, x2, y1, y2, time, vertical;
        Item(int x1, int y1, int x2, int y2, int time, int v){
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.time = time;
            this.vertical = v;
        }
    }
    
    public int solution(int[][] board) {
        int answer = 0;
        Queue<Item> q = new LinkedList<>();
        int[][] op = {{1,0},{-1,0},{0,1},{0,-1}};
        boolean[][][] visited = new boolean[board.length][board.length][2];
        
        q.offer(new Item(0, 0, 0, 1, 0, 0));
        
        while(!q.isEmpty()){
            Item item = q.peek();
            q.poll();
            
            if(item.x1 < 0 || item.x1 >= board.length || item.y1 < 0 || item.y1 >= board.length ||
                   item.x2 < 0 || item.x2 >= board.length || item.y2 < 0 || item.y2 >= board.length){
                continue;
            }
            
            if(board[item.x1][item.y1] == 1 || board[item.x2][item.y2] == 1){
                continue;
            }
            
            if(visited[item.x1][item.y1][item.vertical] && 
              visited[item.x2][item.y2][item.vertical])
                continue;
                
            if((item.x1 == board.length - 1 && item.y1 == board.length - 1) ||
               (item.x2 == board.length - 1 && item.y2 == board.length - 1)){
                answer = item.time;
                break;
            }
            
            
            visited[item.x1][item.y1][item.vertical] = true;
            visited[item.x2][item.y2][item.vertical] = true;
            
            for(int i = 0; i < op.length; i++){
                int n_x1 = item.x1 + op[i][0];
                int n_y1 = item.y1 + op[i][1];
                int n_x2 = item.x2 + op[i][0];
                int n_y2 = item.y2 + op[i][1];
 
                q.offer(new Item(n_x1, n_y1, n_x2, n_y2, item.time + 1, item.vertical));
            }
            
            if(item.vertical == 1){
                if(item.y1 - 1 >= 0 && board[item.x1][item.y1 - 1] == 0 && board[item.x2][item.y2 - 1] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1, item.y1 - 1, item.time + 1, 0));
                    q.offer(new Item(item.x2, item.y2, item.x2, item.y2 - 1, item.time + 1, 0));
                }
                
                if(item.y1 + 1 <= (board.length - 1) && 
                   board[item.x1][item.y1 + 1] == 0 && board[item.x2][item.y2 + 1] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1, item.y1 + 1, item.time + 1, 0));
                    q.offer(new Item(item.x2, item.y2, item.x2, item.y2 + 1, item.time + 1, 0));                    
                }
            }else{
                if(item.x1 - 1 >= 0 && board[item.x1 - 1][item.y1] == 0 &&
                  board[item.x2 - 1][item.y2] == 0){            
                    q.offer(new Item(item.x1, item.y1, item.x1 - 1, item.y1, item.time + 1, 1));
                    q.offer(new Item(item.x2, item.y2, item.x2 - 1, item.y2, item.time + 1, 1));
                }
                
                if(item.x1 + 1 <= (board.length - 1) && board[item.x1 + 1][item.y1] == 0 &&
                  board[item.x2 + 1][item.y2] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1 + 1, item.y1, item.time + 1, 1));
                    q.offer(new Item(item.x2, item.y2, item.x2 + 1, item.y2, item.time + 1, 1));    
                }
            }
        }
 
        return answer;
    }
}