[Java] 2021 위클리 챌린지 11주차 - 아이템 줍기

테두리와 안쪽을 구분해야 한다. 

단순하게 좌표의 길이를 2배로 키우면 테두리와 안쪽을 구분하기가 쉬워진다.

1. (짝수, 짝수) 는 점

2. (짝수, 홀수) 와 (홀수, 짝수)는 선분 위

3. (홀수, 홀수)는 내부가 된다.

먼저 모든 사각형을 1로 채워준 다음, 내부를 0으로 채워주면 제일 바깥쪽 테두리만 남게 된다.

이 이후에는 BFS를 통해서 얼마나 걸리는지 확인해주면 된다. 2배로 키워놨기 때문에 정답은 2로 나눈 값이 된다.

class Point{
    int x;
    int y;
    int depth;
    public Point(int x, int y, int depth){
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        int n = 105;
        int m = 105;

        int[][] board = new int[n][m];

        int numR = rectangle.length;

        //사각형을 1로 채움
        for(int i = 0; i < numR; i ++){
            int[] r = rectangle[i];
            for(int x = r[0] *2; x <= r[2] *2; x ++){
                for(int y = r[1] * 2; y <= r[3] * 2; y ++){
                    board[x][y] = 1;
                }
            }
        }
        //안쪽을 0으로 채움
        for(int i = 0; i < numR; i ++){
            int[] r = rectangle[i];
            for(int x = r[0] *2 + 1; x <= r[2] *2 - 1; x ++){
                for(int y = r[1] * 2 + 1; y <= r[3] * 2 - 1; y ++){
                    board[x][y] = 0;
                }
            }
        }
        boolean[][] visited = new boolean[n][m];

        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        Point start = new Point(characterX * 2, characterY * 2, 0);
        Queue<Point> q = new LinkedList<>();
        visited[characterX * 2][ characterY*2] = true;
        q.add(start);
        
        while(!q.isEmpty()){
            Point front = q.poll();
            if(front.x == itemX * 2 && front.y == itemY *2){
                answer = front.depth;
                break;
            }
            for(int k = 0; k < 4; k ++){
                int nx = dx[k] + front.x;
                int ny = dy[k] + front.y;
                if(!visited[nx][ny] && board[nx][ny] == 1){
                    q.add(new Point(nx,ny, front.depth + 1));
                    visited[nx][ny] = true;
                }
            }
        }
        return answer / 2;
    }
}