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

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

1. 직사각형 배열을 순차대로 입력받아 이차원 배열 map에 표시 (각 길이를 2배로, 모서리와 내부 구분)
2. 시작 위치 값을 큐에 넣으며 BFS 탐색 시작
3. 결과로 얻은 길이 값을 2로 나눈 후 반환

 전체적인 문제의 흐름은 BFS이기에 탐색 과정 자체는 쉽지만, 갈 수 있는 길이 겹쳐진 직사각형의 모서리면서 외부 쪽만 갈 수 있기 때문에 이를 해결하는 것이 제일 관건이다.

 우선 입력받은 직사각형 정보가 담긴 배열들을 순차대로 입력받아 탐색을 진행할 이차원 배열 위에 그리는 데, 이 때 직사각형의 모서리인 부분과 내부 부분을 다르게 표시하며, 특히 모서리 부분을 표시할 때 해당 부분이 다른 직사각형 내부라면 이를 따로 표시하지 않는 것으로 진행한다. 이렇게 되면 최종 이차원 배열이 겹치진 직사각형들의 최외곽 모서리만 1로 표시가 된다.

 그 다음 해결할 문제는 좌표 상으론 하나 차이지만 인접하지 않은 좌표를 구분해야 하는 경우이다.

 문제 속 예시 그림 중 하나를 보면 좌표 (3, 5)와 (3, 6)을 볼 때, 좌표 상으론 인접하나 각각이 다른 직사각형에 속해 있어 BFS 탐색 시 이를 바로 넘어갈 수 없게 방지해야 한다. 이런 경우 해결 방법으로 전체적인 직사각형의 길이들을 2배로 늘려버리면 되는데, 이러면 앞선 (3, 5)와 (3, 6)의 좌표들이 (6, 10)과 (6, 12)가 되며 해당 사이를 구분 지어줄 수 있기 때문이다. 이렇게 길이를 늘린 후 BFS 탐색을 하고 나서 최종적으로 얻은 답을 2로 나누어주면 된다.

 추가적인 팁으로, 앞선 예시들의 좌표의 원점이 모두 좌측 하단에서 시작하는데 이를 굳이 2차원 배열에 동일한 그림으로 옮겨 표시할 필요는 없다. 결국 얻은 그림이 기존 좌표 그림을 뒤집거나한 대칭 이동한 경우에 불가하기 때문에, 길이 상으론 답이 변하지 않아 좌표를 굳이 변환하거나 할 필요는 없다.

class Solution {
    int[][] map = new int[101][101];
    Queue<Point> q = new LinkedList<>();

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 99999999;

        for (int i = 0; i < rectangle.length; i++) {//map에 표시
            int startX = 2 * rectangle[i][0], startY = 2 * rectangle[i][1], endX = 2 * rectangle[i][2], endY = 2 * rectangle[i][3];

            for (int r = startY; r <= endY; r++) {
                for (int c = startX; c <= endX; c++) {
                    if (r == startY || r == endY || c == startX || c == endX) {//현 지점이 모서리라면
                        if (map[r][c] != 2) {//다른 직사각형의 내부가 아니라면
                            map[r][c] = 1;
                        }
                    }
                    else {//현 지점이 직사각형의 내부인 경우
                        map[r][c] = 2;
                    }
                }
            }
        }

        q.add(new Point(characterY * 2, characterX * 2, 0));//큐에 초기값 입력

        while (!q.isEmpty()) {//bfs
            Point here = q.poll();

            if (here.r < 0 || here.r > 100 || here.c < 0 || here.c > 100 || map[here.r][here.c] != 1)
                continue;

            if (here.r == itemY * 2 && here.c == itemX * 2)
                answer = Math.min(answer, here.length);

            map[here.r][here.c] = 3;

            q.add(new Point(here.r + 1, here.c, here.length + 1));
            q.add(new Point(here.r - 1, here.c, here.length + 1));
            q.add(new Point(here.r, here.c + 1, here.length + 1));
            q.add(new Point(here.r, here.c - 1, here.length + 1));
        }

        return answer / 2;//각 좌표를 2배로 늘렸기 때문에 답을 2로 나눠 반환
    }

    class Point {//위치 정보 클래스
        int r, c, length;

        public Point(int r, int c, int length) {
            this.r = r;
            this.c = c;
            this.length = length;
        }
    }
}

결과