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

 

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

프로그래머스

 

문제 설명: 여러 직사각형들이 놓여져 있을 때 겹쳐지는 부분을 제외하고 각 변들을 탐색해서 BFS를 수행하는 문제입니다.

 

제가 생각했던 풀이는 아래와 같습니다.

1. 격자에 각 직사각형들을 색칠한다. (테두리: 1, 내부 -1)

2. 직사각형을 색칠할 때 이미 내부(-1)로 색칠되어 있다면 건너뛴다.

3. 주어진 시작점에서 시작해 색칠된 직사각형들의 1값을 bfs탐색을 통해 주어진 item 좌표로 이동할 때 걸리는 이동거리를 구한다.

 

하지만 이 부분에서 주의할 점은 다음과 같습니다.

색칠된 테두리의 길이가 1일 때인데요, 

 

위의 그림에서 각 위 로직에 따라 테두리를 빨간색 x표로 표시했습니다.

이때, bfs를 수행하게 되면 화살표로 이동하는 것을 막을 수 없습니다.. 따라서 정답보다 적은 수로 답이 구해지게 됩니다.

 

이를 방지하기 위한 방법으로 모든 직사각형의 크기를 2배씩 늘리는 방법을 생각할 수 있습니다.

위 그림의 직사각형들의 크기를 각각 2배씩 늘려보면 아래 그림과 같이 되는데요,

 

이렇게 된다면 위 그림과 같이 해당 화살표에 대한 탐색을 할 일이 없게 됩니다.

 

따라서 주어진 직사각형들의 좌표를 모두 2배씩 크기를 늘리고 주어진 캐릭터와 아이템의 좌표 또한 2배 하여 나온 답을 2로 나누어 준다면 정답임을 알 수 있습니다.

 

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    int[] dx = new int[]{1, 0, -1, 0};
    int[] dy = new int[]{0, 1, 0, -1};
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {

        int[][] map = new int[101][101];
        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 2;

        for(int[] r: rectangle){

            r[0] *= 2;
            r[1] *= 2;
            r[2] *= 2;
            r[3] *= 2;

            for(int x = r[0]; x <= r[2]; x++){
                for(int y = r[1]; y <= r[3]; y++){
                    //라인일때
                    if(x == r[0] || x == r[2] || y == r[1] || y == r[3]) {
                        if(map[x][y] == -1) continue;
                        map[x][y] = 1;
                    }
                    else map[x][y] = -1; //내부 표시
                }
            }
        }

        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[101][101];

        queue.add(new int[]{characterX, characterY, 0}); //좌표 이동거리
        visited[characterX][characterY] = true;

        while(!queue.isEmpty()){

            int[] cur = queue.poll();
            if(cur[0] == itemX && cur[1] == itemY) return cur[2] / 2;

            for(int dir = 0; dir < 4; dir++){

                int nx = cur[0] + dx[dir];
                int ny = cur[1] + dy[dir];

                if(nx < 0 || ny < 0 || nx >= 101 || ny >= 101) continue;
                if(visited[nx][ny] || map[nx][ny] != 1) continue;
                queue.add(new int[]{nx, ny, cur[2] + 1});
                visited[nx][ny] = true;
            }
        }
        return -1;
    }
}