[Java] 16973 직사각형 탈출

문제

문제
크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 
격자판은 크기가 1×1인 칸으로 나누어져 있다. 
격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 

직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 
이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다.
직사각형은 벽이 있는 칸에 있을 수 없다. 
또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

입력
첫째 줄에 격자판의 크기 N, M이 주어진다. 
둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다.
0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

출력
첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

문제 풀이

BFS로 풀 수 있는 문제이다. 한 칸 이동 할 때 마다 사각형이 벽에 막히는 지 확인을 해야하는데 매번 사각형이 범위 안에 있거나 벽이 없는지 검사하면 시간 초과가 날 수 있다.

벽의 위치를 미리 저장해 놓고 벽이 이동할 때마다 벽의 좌표가 사각형 범위 안에 있는지 검사는 형태로 작성한다.

자세한 로직은 주석으로 작성한다.

 

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class N16973 {
    
    // 격자판 크기, 직사각형 크기, 답
    private static int N, M, width, height, ans;
    // 격자판
    private static int[][] board;
    // 시작, 종료 좌표
    private static int[] pos;
    // 벽이 있는 좌표
    private static final List<Pos> list = new ArrayList<>();

    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};

    // 좌표 클래스
    private static class Pos{
        private final int x;
        private final int y;

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

        public int getX(){
            return this.x;
        }

        public int getY(){
            return this.y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 격자판 크기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 격자판
        board = new int[N + 1][M + 1];
        for(int i = 1; i <= N; i++){
            String[] oneLine = br.readLine().split(" ");
            for(int j = 0; j < oneLine.length; j++){
                board[i][j+1] = Integer.parseInt(oneLine[j]);
                if(board[i][j] == 1) {
                    board[i][j] = -1;
                    list.add(new Pos(i, j));
                }
            }
        }

        st = new StringTokenizer(br.readLine(), " ");

        // 격자판 내부의 직사각형과 시작점, 도착점
        width = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
        pos = new int[4];

        for(int i = 0; i < pos.length; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }

        ans = -1;
        bfs();
        System.out.println(ans);
    }

    public static void bfs(){
        Queue<Pos> queue = new LinkedList<>();
        boolean[][] checked = new boolean[N+1][M+1];

        // 시작점 큐에 담고 check
        queue.add(new Pos(pos[0], pos[1]));
        checked[pos[0]][pos[1]] = true;

        // 큐가 빌때까지 반복
        while(!queue.isEmpty()){
            // 좌표 값을 하나 꺼낸다.
            Pos p = queue.poll();
            
            int curX = p.getX();
            int curY = p.getY();

            // 뽑은 현재 좌표가 도착점이라면 ans를 갱신하고 종료
            if(curX == pos[2] && curY == pos[3]){
                ans = board[curX][curY];
                return;
            }

            // 현재 좌표를 기준으로 상하좌우를 검사
            for(int i = 0; i < 4; i++){
                int nx = dr[i] + curX;
                int ny = dc[i] + curY;
                
                // 검사하는 좌표가 격자판 범위를 벗어나거나 이미 체크한 좌표일 경우 생략
                if(nx < 1 || ny < 1 || nx > N || ny > M || checked[nx][ny])
                    continue;
                // 이동 위치에 벽이 있을 경우 생략
                if(!isMove(nx, ny))
                    continue;

                // 검사 값 도착 최소 값 기록을 아직 안했다면 현재 값 + 1로 저장한다.
                if(board[nx][ny] == 0) {
                    queue.add(new Pos(nx, ny));
                    checked[nx][ny] = true;
                    board[nx][ny] = board[curX][curY] + 1;
                }
            }
        }
    }

    // 이동 가능한지 검사하는 메소드
    public static boolean isMove(int x, int y){
        // 직사각형이 격자판 범위를 벗어나면 이동 불가
        if(x + width - 1 > N || y + height -1 > M)
            return false;

        // 벽이 있는 좌표를 하나 씩 꺼내서 검사
        for (Pos p : list) {
            int px = p.getX();
            int py = p.getY();

            // 해당 벽이 이동한 사각형의 범위 안에 있다면 이동 불가
            if (px >= x && px <= x + width - 1 && py >= y && py <= y + height - 1) {
                return false;
            }
        }

        // 위의 조건을 다 통과했을 경우 이동 가능
        return true;
    }
}