문제

문제 접근

• 문제에서 주어진 그래프의 최대 크기는 50*50 사이즈
• 그래프에서 순차적으로 도형들의 좌표를 통하여 테두리를 1, 안쪽을 2, 아무것도 없는 부분을 1 로 저장합니다

즉, 아래와 같은 함수를 통해 순차적으로 도형을 그래프에 채워주었습니다

public static void fill(int[] coords){
        // x 축 채우기
        for (int i = 0; i <= coords[2]-coords[0]; i++) {
            int target = coords[0]+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌

            if(map[coords[1]][target] == 0) map[coords[1]][target] = 1;
            if(map[coords[3]][target] == 0) map[coords[3]][target] = 1;
            // 테두리 부분을 피해서 안쪽 부분만 채워줌
            if(target!=coords[0] && target!=coords[2]){
                // 그 안쪽은 2로 채워줌, 만약 너비가 2초과일 경우에만 해당
                for (int j = coords[1]+1; j < coords[3] ; j++) {
                    map[j][target] = 2;
                }
            }
        }
        // y 축 채우기
        for (int i = 0; i < coords[3]-coords[1]; i++) {
            int target = coords[1]+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌
            if(map[target][coords[0]] == 0) map[target][coords[0]] = 1;
            if(map[target][coords[2]] == 0) map[target][coords[2]] = 1;

        }
    }

아래는 bfs 함수입니다

public static void bfs(Point point){
        Queue<Point> queue = new LinkedList<>();
        queue.add(point); // 큐에 시작지점을 저장
        map[point.y][point.x] = 0; // 시작지점 방문처리

        while(!queue.isEmpty()){
            Point now = queue.poll(); // 큐에서 현재 위치를 꺼내온다
            for (int i = 0; i < 4; i++) {
                int nx = dx[i]+now.x;
                int ny = dy[i]+now.y;

                if(nx <= 50 && nx > 0 && ny <= 50 && ny > 0 && map[ny][nx]==1){
                    map[ny][nx] = map[now.y][now.x]+1;
                    queue.add(new Point(nx, ny));
                }
            }
        }
    }

다른 테스트케이스의 경우 모두 통과하였지만 다음과 같은 경우에는 예외가 생깁니다

다음과 같이 안쪽을 채워줄수 없는 상황, 즉 폭이 2인 경우에는 형광펜 라인을 따라 bfs가 수행되어 원하는 값을 가져올 수 없었습니다

🤔 조금 난해하겠지만 그래프의 크기를 2배로 늘리고, 각 직사각형의 사이즈를 두배로 늘린다면 해결해 볼 수 있지 않을까 하는 생각이 들었습니다

즉, 2x2의 사각형의 경우 4x4 로 표현하여 확실하게 안쪽을 채워주는 법을 말이죠

방법은 간단합니다. 기존 그래프의 최대너비를 100x100으로 설정하고 fill 부분을 다음과 같이 바꾸어 줍니다

public static void fill(int[] coords){
        int x1 = 2*coords[0];
        int x2 = 2*coords[2];
        int y1 = 2*coords[1];
        int y2 = 2*coords[3];

        // x 축 채우기
        for (int i = 0; i <= x2-x1; i++) {
            int target = x1+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌

            if(map[y1][target] == 0) map[y1][target] = 1;
            if(map[y2][target] == 0) map[y2][target] = 1;
            // 테두리 부분을 피해서 안쪽 부분만 채워줌
            if(target!=x1 && target!=x2){
                // 그 안쪽은 2로 채워줌, 만약 너비가 2초과일 경우에만 해당
                for (int j = y1+1; j < y2 ; j++) {
                    map[j][target] = 2;
                }
            }
        }
        // y 축 채우기
        for (int i = 0; i < y2-y1; i++) {
            int target = y1+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌
            if(map[target][x1] == 0) map[target][x1] = 1;
            if(map[target][x2] == 0) map[target][x2] = 1;

        }
    }

각 x,y 좌표를 2배 늘려줍니다
이렇게 한다면 다음과 같이 폭이 1이더라도 표현을 해줄 수 있습니다

어떻게 최소값임을 보장하느냐?

너비우선 탐색인 BFS 에서 이어져있는 부분을 너비 우선으로 탐색하게 됩니다.
그로 인해 자연스럽게 이전값의 +1 을 받았던 곳에서는 방문처리가 되었기 때문에 재방문 하지 않게 되고 먼저 너비우선으로 퍼졌을 때 자연스럽게 최소값을 가지는 값이 먼저 도착지에 오게 되므로 최소값을 보장받을 수 있습니다.
🤷‍♂️ DFS 라면? DFS 로 설계 하였다면 최대 깊이까지 가서 (도착지점) 최소값을 업데이트하는 방법, 그리고 백트래킹할 수 있도록 visited라는 배열을 따로 두었을 것입니다

즉, BFS 를 사용한다면 도착지점에 도달하였을 때 이미 최소값을 보장 받습니다

---

최종코드

import java.util.*;
class Solution {
    static int[][] map = new int[101][101];
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    
    static class Point{
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void fill(int[] coords){
        int x1 = 2*coords[0];
        int x2 = 2*coords[2];
        int y1 = 2*coords[1];
        int y2 = 2*coords[3];

        // x 축 채우기
        for (int i = 0; i <= x2-x1; i++) {
            int target = x1+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌

            if(map[y1][target] == 0) map[y1][target] = 1;
            if(map[y2][target] == 0) map[y2][target] = 1;
            // 테두리 부분을 피해서 안쪽 부분만 채워줌
            if(target!=x1 && target!=x2){
                // 그 안쪽은 2로 채워줌, 만약 너비가 2초과일 경우에만 해당
                for (int j = y1+1; j < y2 ; j++) {
                    map[j][target] = 2;
                }
            }
        }
        // y 축 채우기
        for (int i = 0; i < y2-y1; i++) {
            int target = y1+i;
            // 해당 칸이 0일 경우에만 1로 바꾸어줌
            if(map[target][x1] == 0) map[target][x1] = 1;
            if(map[target][x2] == 0) map[target][x2] = 1;

        }
    }
    
    public static void bfs(Point point, Point endPoint){
        Queue<Point> queue = new LinkedList<>();
        queue.add(point); // 큐에 시작지점을 저장
        map[point.y][point.x] = 0; // 시작지점 방문처리

        while(!queue.isEmpty()){
            Point now = queue.poll(); // 큐에서 현재 위치를 꺼내온다
            for (int i = 0; i < 4; i++) {
                int nx = dx[i]+now.x;
                int ny = dy[i]+now.y;

                if(nx <= 100 && nx >= 0 && ny <= 100 && ny >= 0 && map[ny][nx]==1){
                    map[ny][nx] = map[now.y][now.x]+1;
                    queue.add(new Point(nx, ny));
                    if(ny == endPoint.y && nx == endPoint.x) return;
                }
            }
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        for (int[] ints : rectangle) {
            fill(ints);
        }
        bfs(new Point(2*characterX, 2*characterY), new Point(2*itemX, 2*itemY));
        int answer = map[2*itemY][2*itemX]/2;
        
        return answer;
    }
}