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

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

코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int MAX_X = 101;
    static int MAX_Y = 101;

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] map = new int[MAX_X][MAX_Y];
        int[][] distance = new int[MAX_X][MAX_Y];

        // 현재 위치 기준 상, 우, 하, 좌의 좌표
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        // 도형 테두리는 1, 안쪽 부분은 2씩 더함
        for (int[] rec : rectangle) {
            rec[0] *= 2;
            rec[1] *= 2;
            rec[2] *= 2;
            rec[3] *= 2;
            for (int i = rec[0]; i <= rec[2]; i++) {
                for (int j = rec[1]; j <= rec[3]; j++) {
                    if (i == rec[0] || i == rec[2]
                            || j == rec[1] || j == rec[3]) {
                        // 도형의 테두리인 경우
                        if (map[i][j] != 1) {
                            map[i][j] += 1;
                        }
                    } else {
                        map[i][j] += 2;
                    }
                }
            }
        }

        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 2;

        // BFS
        Queue<Point> queue = new LinkedList<>();

        queue.offer(new Point(characterX, characterY));
        map[characterX][characterY] = 0;
        distance[characterX][characterY] = 0;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nowX = point.x + dx[i];
                int nowY = point.y + dy[i];

                if (nowX >= 0 && nowX < MAX_X
                        && nowY >= 0 && nowY < MAX_Y
                        && map[nowX][nowY] == 1) {
                    map[nowX][nowY] = 0;

                    distance[nowX][nowY] = distance[point.x][point.y] + 1;
                    if (nowX == itemX && nowY == itemY) {
                        return distance[nowX][nowY] / 2;
                    }

                    queue.offer(new Point(nowX, nowY));
                }
            }
        }

        return -1;
    }
}

풀이

여러 개의 직사각형으로 이루어진 도형을 2차원 배열에서 표현할 때 테두리 부분(도형의 가장 바깥쪽)은 1로, 나머지 안쪽 부분은 2씩 더해준다.

입력으로 [[2,1,7,5],[6,4,10,10]]일 때 도형은 아래와 같이 저장될 것이다. (이해를 돕기 위해 x, y 좌표 평면에서 표시했다.)

이제 출발 위치(characterX, characterY)로부터 도착 위치(itemX, itemY)까지 숫자 1이 나오는 경로로만 BFS/DFS로 탐색하면 된다.

다만 여기서 문제되는 케이스가 있다. 아래의 그림과 같이 상하좌우에 위치한 1의 개수가 2개 이상인 경우에는 원하지 않는 경로로 탐색을 할 수 있게 된다.

이를 해결하기 위해 격자의 한 칸 길이를 1이 아니라 0.5라고 생각한다. 즉, 모든 좌표 단위에 2배를 해줘서 계산하면 이 예외 케이스를 해결할 수 있다.