[lv.3] 아이템 줍기

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

• 문제
  
  이때, 직사각형을 전부 겹쳐서 생기는 가장자리만을 이동할 수 있다.
  

• 풀이
  1) 주어진 좌표로 4점을 모두 구한 뒤, 4점을 2배로 만든다.
  2) 만든 4점을 이용해 선을 잇는다. 이때 선 부분은 1, 그 안의 사각형 내부는 2로 한다. 이때 모든 4점은 해당 채울 칸이 2가 아닌 경우에 1로 채운다.
  3) cx, cy에서부터 시작하는 BFS를 돌리고, 해당 값/2를 리턴한다.

• 4점을 2배로 만드는 이유
  : 예시 1의 경우
  이 부분을 2배로 만들지 않을 경우

0 1 0 0 0
0 1 1 1 0 <------- 이어지면 안될 부분이 이어진다.
0 0 1 1 0
1 1 1 0 0

dx, dy가 1칸식 이동한다고 할때, 이어지지 않은 부분으로 이동하게 된다.
dx, dy를 2배로 늘려도 위의 현상은 일어난다.

• 코드

import java.util.*;

class Solution {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map = new int[102][102];
    static boolean[][] check = new boolean[102][102];
    public int solution(int[][] rectangle, int cx, int cy, int ix, int iy) {
        int answer = 0;
        for(int i=0; i<rectangle.length; i++){
            int[] now = rectangle[i];
            for(int j=0; j<now.length; j++){
                now[j] *= 2;
            }
            makeLine(now);
        }
        answer = bfs(cx*2, cy*2, ix*2, iy*2);
        return answer;
    }
    public void makeLine(int[] xy){
        for(int i=xy[0]; i<=xy[2]; i++){
            for(int j=xy[1]; j<=xy[3]; j++){
                if((i==xy[0] || i==xy[2] || j==xy[1] || j==xy[3]) && (map[i][j]!=2)) map[i][j]=1;
                else map[i][j]=2;
            }
        }
    }
    public int bfs(int cx, int cy, int ix, int iy){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{cx, cy, 0});
        check[cx][cy] = true;
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            if(now[0]==ix && now[1]==iy) return now[2]/2;
            for(int i=0; i<4; i++){
                int nx = now[0]+dx[i];
                int ny = now[1]+dy[i];
                if(nx<0 || ny<0 || nx>=102 || ny>=102) continue;
                if(map[nx][ny]!=1 || check[nx][ny]) continue;
                queue.add(new int[]{nx, ny, now[2]+1});
                check[nx][ny] = true;
            }
        }
        return 0;
    }
}