이 문제로 이틀을 고민했는데
어쩔 수 없이 사람들의 풀이를 보고 힌트를 얻어 풀어보았다.

접근

1) DFS로 풀것이다.

2) 테두리를 true 안에 빈곳을 false로 채울것이다.

즉 위와 같이 모든 사각형을 테두리와 내부를 모두 true로 칠한다.

그 다음 각 사각형에 대해서 내부를 false로 바꿔준다.

만약에 위와 같이 한번에 칠하고(true로 만들고) 한번에 내부를 비어주지(flase로 만들지) 않고 하나 칠하고 하나 비우면

위와 같이 사각형 내부에 다시 true가 만들어진다.

따라서 코드는 아래와 같다.

  static void makeMap(int[][] rectangle){
        
        for(int i=0;i<rectangle.length;i++){
            int row1 = rectangle[i][1]*2 ;
            int col1 = rectangle[i][0]*2 ;
            int row2 = rectangle[i][3] *2;
            int col2 = rectangle[i][2] *2;
            make_retangle(row1,col1,row2,col2);
        }
        
         for(int i=0;i<rectangle.length;i++){
            int row1 = rectangle[i][1]*2 ;
            int col1 = rectangle[i][0]*2 ;
            int row2 = rectangle[i][3]*2 ;
            int col2 = rectangle[i][2]*2 ;
            make_zero(row1,col1,row2,col2);
        }
        
    }

 static void  make_retangle(int row1, int col1,int row2,int col2){
        for(int i=row1;i<=row2;i++){
            for(int j=col1;j<=col2;j++){
                map[i][j]=true;
            }
        }
    }
    
    static void  make_zero(int row1, int col1,int row2,int col2){
        for(int i=row1+1;i<row2;i++){
            for(int j=col1+1;j<col2;j++){
                map[i][j]=false;
            }
        }
    }
    

3) 근데 문제가 있다 인접한 사각형에서 문제가 발생한다.

우리가 생각하기를 윤곽선이 저렇게 갈거 같지만
컴퓨터는 붙어있는 true면 어디든 갈수있다.

참고로 DFS는 상하좌우로 한칸씩 움직이며 거기가 true이면 무조건 전진하기 때문에 컴퓨터 입장에서는 어디든 다 갈 수 있다!

따라서 true와 false를 저장하는 즉 윤곽선에 대한 정보를 저장하는 곳의 크기를 가로 2배, 세로 2배씩 늘려준다.

따라서 들어오는 시작위치 및 아이템 위치 모두 2배씩 해준다.

마지막에 DFS에 대한 값은 2배 늘려줬으니 2로 나눠준다.

문제에서 주어주기를 들어오는 x와 y가 0부터 50사이의 숫자이므로
거기에 두배인 101에서 여유있게 103으로 해줬다.

따라서 관련 코드는 아래와 같다.

 public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        map = new boolean[103][103];
        visit = new boolean[103][103];
        answer_list = new ArrayList<>();
        
        characterX = characterX*2;
        characterY = characterY*2;
        itemX = itemX*2;
        itemY = itemY*2;
        
        makeMap(rectangle);
        
        visit[characterY][characterX]=true;
        DFS(characterX,characterY,itemX,itemY,0);
        
        Collections.sort(answer_list);
        
        
        int answer =answer_list.get(0)/2;
        return answer;
    }

---

풀이과정

전체 풀이는 아래와 같다.

import java.util.*;
import java.io.*;


class Solution {
    
    
    static boolean[][] map;
    static boolean[][] visit;
    
    static int[] cx={0,0,-1,1};
    static int[] cy={1,-1,0,0};
    
    static ArrayList<Integer> answer_list;
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        map = new boolean[103][103];
        visit = new boolean[103][103];
        answer_list = new ArrayList<>();
        
        characterX = characterX*2;
        characterY = characterY*2;
        itemX = itemX*2;
        itemY = itemY*2;
        
        makeMap(rectangle);
        
        visit[characterY][characterX]=true;
        DFS(characterX,characterY,itemX,itemY,0);
        
        Collections.sort(answer_list);
        
        
        int answer =answer_list.get(0)/2;
        return answer;
    }
    
    static void makeMap(int[][] rectangle){
        
        for(int i=0;i<rectangle.length;i++){
            int row1 = rectangle[i][1]*2 ;
            int col1 = rectangle[i][0]*2 ;
            int row2 = rectangle[i][3] *2;
            int col2 = rectangle[i][2] *2;
            make_retangle(row1,col1,row2,col2);
        }
        
         for(int i=0;i<rectangle.length;i++){
            int row1 = rectangle[i][1]*2 ;
            int col1 = rectangle[i][0]*2 ;
            int row2 = rectangle[i][3]*2 ;
            int col2 = rectangle[i][2]*2 ;
            make_zero(row1,col1,row2,col2);
        }
        
    }
    
    static void  make_retangle(int row1, int col1,int row2,int col2){
        for(int i=row1;i<=row2;i++){
            for(int j=col1;j<=col2;j++){
                map[i][j]=true;
            }
        }
    }
    
    static void  make_zero(int row1, int col1,int row2,int col2){
        for(int i=row1+1;i<row2;i++){
            for(int j=col1+1;j<col2;j++){
                map[i][j]=false;
            }
        }
    }
    
    
    static void DFS(int characterX, int characterY,int itemX,int itemY,int level){
        if(characterX==itemX && characterY==itemY){
             answer_list.add(level);
             visit[characterY][characterX]=false;
             return;          
        }else{
            for(int i=0;i<4;i++){
                int row = characterY+cy[i];
                int col = characterX+cx[i];
                if(row>=0 && row<103 && col>=0&& col<103&&visit[row][col]==false){
                    if(map[row][col]==true){
                        visit[row][col]=true;
                        DFS(col,row,itemX,itemY,level+1);
                    }
                }
            }//for 상하좌우
        }//else
    }//DFS
    
    
    
}