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

-Code

import java.util.*;

class Solution {
    static int[][] map = new int[101][101];
    static boolean[][] visited = new boolean[101][101];
    
    static class PosInfo {
        int row, col, dist;
        
        public PosInfo(int row, int col, int dist) {
            this.row = row;
            this.col = col;
            this.dist = dist;
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        // 사각형 부분 채우기
        for (int[] rectPos : rectangle) {
            int x1 = rectPos[0] * 2;
            int y1 = rectPos[1] * 2;
            int x2 = rectPos[2] * 2;
            int y2 = rectPos[3] * 2;
            
            for (int row = x1; row <= x2; row++) {
                for (int col = y1; col <= y2; col++) {
                    map[row][col] = 1;
                }
            }
        }
        // 테두리만 남기고 파내기
        for (int[] rectPos : rectangle) {
            int x1 = rectPos[0] * 2 + 1;
            int y1 = rectPos[1] * 2 + 1;
            int x2 = rectPos[2] * 2 - 1;
            int y2 = rectPos[3] * 2 - 1;
            
            for (int row = x1; row <= x2; row++) {
                for (int col = y1; col <= y2; col++) {
                    map[row][col] = 0;
                }
            }
        }
        // 시작점 인스턴스 생성
        PosInfo startPos = new PosInfo(characterX * 2, characterY * 2, 0);
        return BFS(startPos, itemX * 2, itemY * 2);
    }
    
    private static int BFS(PosInfo startPos, int itemRow, int itemCol) {
        // 이동 방향 셋팅
        int[] dRow = {-1, 1, 0, 0};
        int[] dCol = {0, 0, -1, 1};
        // 방문 및 덱 셋팅
        visited[startPos.row][startPos.col] = true;
        Deque<PosInfo> deque = new ArrayDeque<>();
        deque.addLast(startPos);
        // 탐색 시작
        while(!deque.isEmpty()) {
            PosInfo nowPos = deque.pollFirst();
            // 아이템이 있는 경우 탈출
            if (nowPos.row == itemRow && nowPos.col == itemCol) {
                return nowPos.dist / 2;
            }
            // 다음 위치 탐색
            for (int i = 0; i < 4; i++) {
                int nextRow = nowPos.row + dRow[i];
                int nextCol = nowPos.col + dCol[i];
                // 이동 가능한 경우
                if (canMove(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    PosInfo nextPos = new PosInfo(nextRow, nextCol, nowPos.dist + 1);
                    deque.addLast(nextPos);
                }
            }
        }
        return -1;
    }
    // 이동 가능한지 확인
    private static boolean canMove(int row, int col) {
        return (0 < row && row < 101) && (0 < col && col < 101) && map[row][col] == 1;
    }
}

처음 접하고 사각형들을 맵에 1로 채우는 것까지는 생각했지만 테두리만 남기는 부분에서 문제가 생겼습니다. 그래서 고민을 하다가 답을 찾지 못해 전부 채운 후 테두리만 남기라는 힌트를 얻고 진행을 했습니다. 하지만 추가적인 문제인 변이 겹쳤을 경우에 세로선을 타고 넘어가야 하지만 (ㅗ) 형태로 만들어져 바로 가로선을 타버리는 문제점을 알게되었고 이를 맵의 크기를 2배로 넓혀봐라는 힌트를 얻고 해결했습니다. 아이디어를 떠올리는게 어려워서 힌트를 2번이나 찾아보게 되어서 아쉬웠습니다.