지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
itemX, itemY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

처음한 생각

누적합 문제인줄알았다. 간단히 누적합 시킨뒤 bfs를 돌리면 해결될줄알았는데. 누적합보다는 그냥 전체 배열을 모두 돌리는게 방법이었다.

bfs를 돌리기전에 배열값을 2배 해줬는데 점과 점으로 계산이 되기때문에 의도치않은 방향으로 값이 넘어가는걸 방지하기위해 거리를 벌려줘야한다.
또한 갈수있는방향이 startX,Y의 양방향 2갈래이다.

코드

import java.util.*;
class Solution {
    int answer = Integer.MAX_VALUE;
    boolean[][] visit;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int[][] map;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        map = new int[102][102];
        visit= new boolean[102][102];
        for(int[] a: rectangle){
            fill(a[0]*2,a[1]*2,a[2]*2,a[3]*2,map);
        }
        bfs(characterX*2,characterY*2,itemX*2,itemY*2);
       
        return answer/2;
    }
    void fill(int x1,int y1,int x2,int y2,int[][] map){
        for(int i=x1; i<=x2; i++){
            for(int j=y1; j<=y2; j++){
                if(map[i][j]==2) continue;
                map[i][j]=2;
                if(i==x1||i==x2||j==y1||j==y2){
                    map[i][j]=1;
                }
            }
        }
    }
    void bfs(int Sx,int Sy,int Ex,int Ey){
        Queue<int[]> q =new LinkedList<>();
        q.add(new int[]{Sx,Sy,0});
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            for(int i=0; i<4; i++){
                int nx= tmp[0]+dx[i];
                int ny= tmp[1]+dy[i];
                if(nx<0||ny<0||nx>=102||ny>=102) continue; 
                if(map[nx][ny]!=1||visit[nx][ny]) continue;       
                
                int count = tmp[2] + 1;
                if(nx==Ex&&ny==Ey){ 
                    answer= Math.min(answer,count);
                    continue;
                }
                visit[nx][ny]= true;
                q.add(new int[]{nx,ny,count});              
            }
        }
    }
}

간단한 문제였는데 누적합에 정신이 팔려서 꽤나 시간을 잡아먹었다.