아이템 줍기

로직짜는게 어렵지 않았는데 시간이 너무 오래걸렸다..
그렇게 잘 짜고 테스트하다가

[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]	1	3	7	8	17

1번 예제에서 막혔다.

저 표시된 부분을 해결할 방법이 떠오르지 않았다;;
그래서 다른 풀이를 참고했는데 그것은 맵을 2배로 키워서 해결하는 방법이었다!

2배로 키우니 오히려 내부에 갇힌 0 으로 표시된 영역에 대한 확인(단절되었으면 1로 만드는)도 필요없었다

import java.util.*;
class Solution {

    final int maxsize = 120;
    int answer = 0;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {

        int[][] map = new int[maxsize][maxsize];

        for(int[] rec : rectangle){

            int lx = rec[0];
            int ly = rec[1];
            int rx = rec[2];
            int ry = rec[3];

            lx*=2;
            ly*=2;
            rx*=2;
            ry*=2;

            for (int i = lx; i <= rx; i++) {
                for (int j = ly; j <= ry; j++) {
                    map[i][j] = 1;
                }
            }
        }

        int[] character = new int[2];
        character[0] = characterX*2;
        character[1] = characterY*2;
        int[] item = new int[2];
        item[0] = itemX*2;
        item[1] = itemY*2;

        int answer = gogo(character, item, map);

        answer = (int)Math.ceil(answer/2f);

        return answer;
    }

    public int gogo(int[] start, int[] end, int[][] map){
        boolean[][] visit = new boolean[maxsize][maxsize];

        Queue<int[]> que = new LinkedList<>();

        que.add(start);
        visit[start[0]][start[1]] = true;

        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        int[][] edir = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};

        boolean find = false;
        while(que.isEmpty() == false) {

            int[] cur = que.poll();

            for (int i = 0; i < 4; ++i) {
                int nx = cur[0] + dir[i][0];
                int ny = cur[1] + dir[i][1];

                if(map[nx][ny] == 0)
                    continue;

                if(visit[nx][ny] == true)
                    continue;

                boolean isBoarder = false;
                for (int j = 0; j < 8; ++j) {
                    int nnx = nx + edir[j][0];
                    int nny = ny + edir[j][1];

                    if(map[nnx][nny] == 0){
                        isBoarder = true;
                        break;
                    }
                }

                if(false == isBoarder)
                    continue;

                if(nx == end[0] && ny == end[1]){
                    find = true;
                    break;
                }

                visit[nx][ny] = true;
                int[] nei = new int[2];
                nei[0] = nx;
                nei[1] = ny;
                que.add(nei);
                answer++;
            }

            if(find)
                break;
        }


        answer = (int)Math.ceil(answer/2f);

        return answer;
    }
    
}