[프로그래머스] 아이템 줍기 - JAVA

문제 링크

문제 정의

• 여러 사각형이 겹쳐진 다각형의 테두리를 따라서 시작 지점에서 도착 지점까지 도달할 수 있는 최소 거리 구하기

제한 사항

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

---

접근 방법

"경로를 따라 이동한다"를 보자마자 BFS DFS를 사용해야 한다는 것을 알았습니다.
가장 중요한 건 "이 경로는 무엇인가" 입니다.
다각형의 테두리가 경로입니다.

그렇기 떄문에 다각형의 테두리를 경로로 구한 후 해당 테두리로 BFS를 구한다면
문제를 해결할 수 있겠다고 생각했습니다.

테두리 경로 구하기

flood fill의 응용으로
다각형의 범위가 아닌 외부 공간은 이동하고
외부인 공간에서 8방향 (상하좌우대각)으로 이동한다면
테두리를 구할 수 있을 것이라 생각했습니다.

문제점: 정확한 테두리의 범위를 구할 수 없음

하지만 위 방법에 문제점이 존재했습니다.
isRectangle로 모든 사각형의 범위를 true로 지정할 때
두 사각형의 좌표 차이가 1이라면 모두 true 처리가 되어서
두 사각형이 분리되어있는지 아닌지를 파악할 수 없습니다.
따라서 정확한 테두리를 찾을 수 없게 됩니다.

X X X X X X X X X X 
X O O O O O O O X X 
X O X X X X X O X X 
X O X X X X X O X X 
X O O O X X O O X X 
X X X O R X O X X X 
X X O O R X O O O X 
X X O X X X X X O X 
X X O O O X O O O X 
X X X X O O O X X X 
X X X X X X X X X X 

위 출력에서 O인 부분이 테두리라고 출력이 되었지만
사실 R 부분까지 테두리가 되어야하지만 테두리에서 누락이 된 경우입니다.

스케일 업 방식 사용

이 문제는 두 사각형이 존재하더라도 범위 차이가 1일 경우
이것이 하나의 사각형인지, 아니면 서로 다른 사각형인지 구분할 수 없는 것이 문제입니다.

그래서 좌표를 2배로 스케일 업을 해서
두 사각형 사이의 공간을 좌표상으로 인식할 수 있도록 만드는 것이 중요합니다.

X X X X X X X X X X X X X X X X X X 
X X X X X X X X X X X X X X X X X X 
X X O O O O O O O O O O O O O X X X 
X X O X X X X X X X X X X X O X X X 
X X O X X X X X X X X X X X O X X X 
X X O X X X X X X X X X X X O X X X 
X X O X X X X X X X X X X X O X X X 
X X O X X X X X X X X X X X O X X X 
X X O O O O O X X X X X O O O X X X 
X X X X X X O X X X X X O X X X X X 
X X X X X X O O O X X X O X X X X X 
X X X X X X X X O X X X O X X X X X 
X X X X O O O O O X X X O O O O O X 
X X X X O X X X X X X X X X X X O X 
X X X X O X X X X X X X X X X X O X 
X X X X O X X X X X X X X X X X O X 
X X X X O O O O O X X X O O O O O X 
X X X X X X X X O X X X O X X X X X 
X X X X X X X X O O O O O X X X X X 
X X X X X X X X X X X X X X X X X X 

위와 같은 출력을 보자면 이전 출력의 좌표를 2배로 했을 때의 테두리입니다.
확실히 좌표가 1 차이인 부분에서도 정확히 구분하며 테두리를 정확하게 출력하는 것을 볼 수 있습니다.

이후 로직은 단순하기 때문에 생략하겠습니다.
스케일 업을 한 후 BFS를 수행하고 정답은 2로 나누게 된다면 문제를 해결할 수 있게 됩니다.

---

코드

import java.util.*;

class Node {
    int y;
    int x;
    int dist;
    
    public Node (int y, int x, int dist) {
        this.y = y;
        this.x = x;
        this.dist = dist;
    }
}

class Solution {
    static boolean[][] surface;
    static boolean[][] isRectangleArea;
    static int[] dy = {-1, 0, 1, 0, -1, -1, 1, 1};
    static int[] dx = {0, -1, 0, 1, -1, 1, -1, 1};
    static int R;
    static int C;
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        init(rectangle);
        return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
    }
    
    // surface 구하기
    static void init(int[][] rectangle) {
        R = 0;
        C = 0;
        // (x, y)
        
        for (int[] arr : rectangle) {
            C = Math.max(C, arr[2]*2);
            R = Math.max(R, arr[3]*2);
        }
        
        isRectangleArea = new boolean[R+2][C+2];
        surface = new boolean[R+2][C+2];
        
        for (int[] arr : rectangle) {
            for (int row = arr[1]*2; row <= arr[3]*2; row++) {
                for (int col = arr[0]*2; col <= arr[2]*2; col++) {
                    isRectangleArea[row][col] = true;
                }
            }
        }
        
        dfs(0, 0, new boolean[R+2][C+2]);
    }
    
    static void dfs(int y, int x, boolean[][] visited) {
        visited[y][x] = true;
        
        for (int d = 0; d < 8; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            
            if (ny < 0 || ny > R+1 || nx < 0 || nx > C+1) continue;
            
            if (isRectangleArea[ny][nx]) {
                surface[ny][nx] = true;
            }
            else if (!visited[ny][nx]) {
                dfs(ny, nx, visited);
            }
        }
    }
    
    static int bfs(int sx, int sy, int ex, int ey) {
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.offer(new Node(sy, sx, 0));
        
        boolean[][] visited = new boolean[R+2][C+2];
        visited[sy][sx] = true;
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            int y = node.y;
            int x = node.x;
            int dist = node.dist;
            
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                
                if (ny < 0 || ny > R+1 || nx < 0 || nx > C+1) continue;
                if (visited[ny][nx] || !surface[ny][nx]) continue;
                if (ny == ey && nx == ex) return (dist + 1) / 2;
                
                visited[ny][nx] = true;
                q.offer(new Node(ny, nx, dist + 1));
            }
        }
        return 0;
    }
}