[프로그래머스/Java] 아이템 줍기(BFS/DFS 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 BFS/DFS 파트 문제 중 하나인 '아이템 줍기'를 자바로 풀어보았다. 

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

프로그래머스

 

 

 문제를 보면 '최단 거리'를 구해야 하므로, BFS를 사용해야겠다는 판단은 쉽게 할 수 있었다. 하지만 어려운 점은 그려진 직사각형들의 가장 바깥쪽으로만 이동해야 한다는 점이다. 그래서 내가 처음에 접근한 방법은 주어진 모든 직사각형의 면적들을 순회하며 각 직사각형의 테두리는 1, 안쪽은 2로 표기하는 방법이다. 하지만 이렇게 하면 가장 바깥쪽이 아닌 각 직사각형의 테두리도 1로 표기되므로, 순회할 때 이미 2인 부분은 1로 재표기하지 않고, 이미 1인 부분은 다시 2로 표기하는 것을 허용했다. 정리하면 아래와 같다.

1. 직사각형의 테두리는 1, 내부는 2로 표기한다.
2. 만약 테두리가 이미 2로 표기되어 있다면 1로 바꾸지 않는다.
3. 내부가 1로 표기되어 있으면 2로 바꾼다.

 

Rectangular 배열이 " [[1,1,7,4], [3,2,5,5], [4,3,6,9], [2,6,8,8]] "로 주어진 경우를 그려보면 아래 그림과 같이 표기할 수 있다. 

첫 번째 직사각형 => 두번째 직사각형 => 끝까지 그린 경우

 그림을 보면, 첫 번째와 두 번째까지는 문제가 없다. 하지만 마지막까지 그린 걸 보면 굵은 빨간 박스 부분이 문제가 된다는 것을 알 수 있다. 테두리를 모두 지나야 하므로, 저 빨간 박스 부분도 거쳐가야 한다. (예시 그림으로 보면 ㄷ자 부분이다.) 하지만 BFS를 사용하다 보니, 바로 빨간 박스 윗부분으로 지나갈 수 있게 된다. 그래서 테두리를 보다 명확하게 해 주기 위해서 배율을 2배로 늘리는 방법을 사용했다. 

 그렇게 하면 빨간색 rectangular의 y좌표는 4~10이 되고, 초록색 rectangular의 y좌표는 12~16이 되므로 둘이 인접하지 않는 것처럼 처리되고, ㄷ자 부분을 문제없이 지날 수 있게 된다. 마지막으로 결과에 1/2배 해준 것을 리턴하면 답이 된다.

import java.util.*;

class Solution {
    public int[][] makeMap(int[][] rectangle) {
        int[][] map = new int[101][101];
        for (int[] rec : rectangle) {
            for (int i = 0; i < 4; i++) rec[i] *= 2;
            
            for (int x = rec[0]; x <= rec[2]; x++) {
                for (int y = rec[1]; y <= rec[3]; y++) {
                    if (x == rec[0] || x == rec[2] || y == rec[1] || y == rec[3]) {
                        if (map[x][y] != 2) map[x][y] = 1;
                    } else map[x][y] = 2;
                }
            } 
        }
        return map;
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        Queue<List<Integer>> que = new LinkedList<>();
        que.offer(Arrays.asList(characterX*2, characterY*2));
        int[][] map = makeMap(rectangle);
        int[][] mov = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while (!que.isEmpty()) {
            int x = que.peek().get(0);
            int y = que.poll().get(1);
            for (int[] m : mov) {
                int curX = x + m[0];
                int curY = y + m[1];
                if (curX < 0 || curX > 100 || curY < 0 || curY > 100) continue;
                if (curX == itemX*2 && curY == itemY*2) return map[x][y]/2;
                if (map[curX][curY] == 1) {
                    que.offer(Arrays.asList(curX, curY));
                    map[curX][curY] = map[x][y]+1;
                }
            }
        }
        return map[itemX*2][itemY*2] / 2 - 1;
    }
}