[백준] 16973번 : 직사각형 탈출 - 자바[Java]

https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

풀이

BFS를 사용해서 최소 이동 횟수를 구하면 된다. BFS를 수행할 때, checkWall() 메서드를 사용하여 직사각형이 이동할 위치에 벽이 있는지 체크한다.

주의할 점으로는, (1, 1)부터 시작하기 때문에 Sr, Sc, Fr, Fc를 저장할 때 -1을 해야 한다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n, m, h, w;
    static int sr, sc, fr, fc;
    static int[][] map;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};

    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());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        sr = Integer.parseInt(st.nextToken()) - 1;
        sc = Integer.parseInt(st.nextToken()) - 1;
        fr = Integer.parseInt(st.nextToken()) - 1;
        fc = Integer.parseInt(st.nextToken()) - 1;

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        q.add(new int[]{sr, sc, 0});
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            if (r == fr && c == fc) {
                return dist;
            }

            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];

                if (nr >= 0 && nr + h <= n && nc >= 0 && nc + w <= m && !visited[nr][nc] && checkWall(nr, nc)) {
                    q.add(new int[]{nr, nc, dist + 1});
                    visited[nr][nc] = true;
                }
            }
        }

        return -1;
    }

    // 직사각형이 이동할 위치에 벽이 있는지 체크한다.
    static boolean checkWall(int r, int c) {
        for (int i = r; i < r + h; i++) {
            for (int j = c; j < c + w; j++) {
                if (map[i][j] == 1) {
                    return false;
                }
            }
        }

        return true;
    }
}