문제

문제 링크

접근

• 가장 먼저 가장자리에 따라 BFS 탐색을 해야 한다는 생각에서 출발하였다.
• 테두리 정보를 쉽게 입력에 따라 배열에 표시하여 쉽게 얻을 수 있을 것 같다 생각하였다.
• 그런데 특정 점 좌표와 채워진 면적 정보를 2차원 배열로 고민하는 과정에 두 용도를 구분하여 2개의 2차원 배열로 정보를 나타내었다.
• 한 좌표에 대해 제 1,2,3,4사분면의 면적이 채워진 여부에 따라 테두리인지 판단하였다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        boolean[][] am = new boolean[51][51];
        int[][] pm = new int[51][51];
        int[][] ds = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        
        for (int[] rec : rectangle) {
            for (int i = rec[1]; i < rec[3]; i++) {
                for (int j = rec[0]; j < rec[2]; j++) {
                    am[i][j] = true;
                }
            }
        }
        
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[51][51];
        q.add(new Point(characterY, characterX, 0));
        visited[characterY][characterX] = true;
        
        while(!q.isEmpty()) {
            Point p = q.poll();
            
            boolean[] isArea = new boolean[5];
            if (inRange(p.r-1, p.c) && am[p.r-1][p.c]) isArea[1] = true;
            if (inRange(p.r-1, p.c-1) && am[p.r-1][p.c-1]) isArea[2] = true;
            if (inRange(p.r, p.c-1) && am[p.r][p.c-1]) isArea[3] = true;
            if (am[p.r][p.c]) isArea[4] = true;
            
            for (int d = 0; d < 4; d++) {
                int nr = p.r + ds[d][0];
                int nc = p.c + ds[d][1];
                
                if (!inRange(nr, nc) || visited[nr][nc]) continue;
                
                if ((d == 0 && ((!isArea[1] && isArea[4]) || (isArea[1] && !isArea[4])))
                    || (d == 1 && ((!isArea[3] && isArea[4]) || (isArea[3] && !isArea[4])))
                    || (d == 2 && ((!isArea[2] && isArea[3]) || (isArea[2] && !isArea[3])))
                    || (d == 3 && ((!isArea[1] && isArea[2]) || (isArea[1] && !isArea[2])))) {
                    
                    if (nr == itemY && nc == itemX) return p.cnt + 1;
                    
                    visited[nr][nc] = true;
                    q.add(new Point(nr, nc, p.cnt + 1));
                }
            }
        }

        return 0;
    }
    
    boolean inRange(int r, int c) {
        return r < 51 && r >=0 && c < 51 && c >= 0;
    } 
    
    class Point {
        int r, c, cnt;
        
        public Point (int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}