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

출처

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

문제

문제 설명이 길지만, 겹쳐진 사각형들의 밖에 드러난 테두리만 따라 item을 가지러 가는 최소 길이를 return하는 문제입니다.

풀이

겹치는 상황이 생길 수 있으므로 배열을 2배로 확장하여 Boolean배열을 만듭니다. 그냥 boolean이 아닌 박스 Boolean배열로 만든 이유는 NULL, FALSE, TRUE 세가지의 상태가 필요하기 때문입니다. Boolean배열의 경우 기본값이 NULL입니다.

필요한 이유는 직사각형 내부를 False로 채우고 변경되지 않게 하기 위함입니다. 조건을 !=false로 걸면 내부에 테두리 정보가 있으면 true로 바뀝니다.

반복문을 통해 테두리를 표시해준 뒤 시작점을 queue에 넣고 bfs를 시작합니다. dx, dy 테크닉을 이용하여 다음 갈수 있는 곳을 queue에 넣어주고 목적지 도착여부를 검사하는 과정을 반복합니다.

그렇게 구해진 answer중 최소값이 해답이 됩니다.

코드

import java.util.*;
class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = Integer.MAX_VALUE;
        Boolean[][] map = new Boolean[102][102];
        int[] dx = new int[] {1, 0, -1, 0};
        int[] dy = new int[] {0, 1, 0, -1};
        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 2;
        for(int i = 0; i < rectangle.length; i++) {
            int[] tmp = rectangle[i];
            for(int j = 0; j < tmp.length; j++) tmp[j] *= 2;
            
            for(int x = tmp[0]; x <= tmp[2]; x++) {
                for(int y = tmp[1]; y <= tmp[3]; y++) {
                    if(map[x][y] != Boolean.FALSE) {
                        map[x][y] = (x == tmp[0] || x == tmp[2] || 
                            y == tmp[1] || y == tmp[3]);
                    }
                }
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        map[characterX][characterY] = Boolean.FALSE;
        queue.add(new int[] {characterX, characterY, 0});
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            if(tmp[0] == itemX && tmp[1] == itemY) {
                answer = Math.min(answer, tmp[2]/2);
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if(isRange(map, nx, ny)) {
                    map[nx][ny] = Boolean.FALSE;
                    queue.add(new int[] {nx, ny, tmp[2]+1});
                }
            }
        }
        
        return answer;
    }
    
    public boolean isRange(Boolean[][] map, int x, int y) {
        return x >= 2 && x <= 100 && y >= 2 && y <= 100 && map[x][y] == Boolean.TRUE;
    }
}