(Java) 프로그래머스 - 아이템 줍기

https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 아이템 줍기

처음에 어떻게 풀어야 할지 감이 안 와서 고민해보다가 다른 분들의 힌트를 봤다. 생활 패턴 고친다고 밤을 새워서 그런지(핑계 맞음ㅎㅎ) 봐도 무슨 말인지 모르겠더라. 짐 싸서 집 가는 길에 백준에서 비슷한 문제를 풀었던 기억이 갑자기 떠올랐다ㅋㅋ. 신기하게도 샤워하거나 산책하면 아이디어가 잘 떠오르는데, 이유는 뭘까?

 

아무튼 DFS나 BFS로 풀 수 있다는 것까진 알았는데, 이번엔 어떻게 테두리만 표시할지 떠오르지 않았다. 결국 다른 분의 풀이를 봤는데, 대단한 사고력이 필요하진 않았고 오히려 방법이 단순했다. 최근에 코테 실력이 많이 는 것 같아서 "나 이제 코테 좀 치나?ㅋㅋ" 싶었는데, 반성했다.

 

결론적으론 나에게 어려운 문제였다.

요약

1. 좌표 및 사각형 영역을 2배로 늘린다
2. 그래프에 모든 사각형의 테두리를 표시한다. (1 vs 0 or true vs false)
3. 사각형의 테두리를 제외한 안쪽 영역(너비)을 빈공간으로 표시한다.
4. 테두리 전체 길이(S)와 시작점에서 도착점(src- dst)까지의 길이를 각각 구한다.
5. 정답: min(S - (src - dst), src - dst)

풀이

1. DFS/BFS로 해결할 수 있다

그래프를 점과 빈공간으로 표시할 때, 테두리만을 나타낼 수 있으면 시작점에서 도착점까지 얼마나 이동했는지를 DFS/BFS로 알 수 있다.

2. 좌표를 늘린다!

테두리를 따라가려면 인접한 1을 탐색하면 된다. 하지만 테두리간 거리가 1이면 위와 같은 상황에서 테두리를 잘못 따라갈 수 있다. 따라서, 좌표를 모두 2배로 늘려서 위와 같은 문제를 예방한다.

3. 어떻게 바깥의 테두리만 표시할 수 있을까?

1. 우선 모든 사각형의 테두리를 표시한다.

2. 테두리 안쪽 영역을 빈공간으로 표시한다. 그럼 사각형에 포함되어 있던 테두리가 제거된다.

코드

class Solution {
    static final int SIZE = 101;
    static boolean[][] board = new boolean[SIZE][SIZE]; // true: 점 

    int[] dR = new int[]{-1, 1, 0, 0};
    int[] dC = new int[]{0, 0, -1, 1};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        // 좌표 2배로 늘리기
        int srcRow = characterY * 2;
        int srcCol = characterX * 2;
        int dstRow = itemY * 2;
        int dstCol = itemX * 2;

        markRect(rectangle); // 그래프에 사각형 테두리만 표시
        
        // + 1: 마지막 위치에서 시작점으로 돌아온 거리
        int totalDistance = findDistance(srcRow, srcCol, srcRow, srcCol, new boolean[SIZE][SIZE], 0) + 1; 
        int distance = findDistance(srcRow, srcCol, dstRow, dstCol, new boolean[SIZE][SIZE], 0);

        return Math.min(distance, totalDistance - distance) / 2;
    }

    private void markRect(int[][] rectangles) {
        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markEdge(firstRow, firstCol, secondRow, secondCol);
        }

        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markSpace(firstRow, firstCol, secondRow, secondCol);
        }
    }

    // 그래프에 테두리 모두 표시
    private void markEdge(int firstRow, int firstCol, int secondRow, int secondCol) {
        for(int row = firstRow; row <= secondRow; row++) {
            board[row][firstCol] = true;
        }
        for(int col = firstCol + 1; col <= secondCol; col++) {
            board[secondRow][col] = true;
        }
        for(int row = secondRow - 1; row >= firstRow; row--) {
            board[row][secondCol] = true;
        }
        for (int col = secondCol - 1; col > firstCol; col--) {
            board[firstRow][col] = true;
        }
    }

    // 테두리를 제외한 사각형 너비 영역을 모두 빈공간으로 표시한다
    private void markSpace(int firstRow, int firstCol, int secondRow, int secondCol) {
        for (int row = firstRow + 1; row < secondRow; row++) {
            for (int col = firstCol + 1; col < secondCol; col++) {
                board[row][col] = false;
            }
        }
    }

    // DFS
    private int findDistance(int row, int col, final int dstRow, final int dstCol, final boolean[][] visited, int count) {
        if (count > 0 && row == dstRow && col == dstCol) {
            return count;
        }

        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {
            int newRow = row + dR[i];
            int newCol = col + dC[i];

            if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && board[newRow][newCol] && !visited[newRow][newCol]) {
                return findDistance(newRow, newCol, dstRow, dstCol, visited, count+1);
            }
        }

        return count;
    }
}