직사각형 탈출

📍 문제 설명

https://www.acmicpc.net/status?user_id=chqdlstjd2&problem_id=16973&from_mine=1 

채점 현황

 

💡 접근

전형적인 BFS 문제

다른 부분은 좌표 하나만 확인하는 것이 아닌 직사각형으로 확인해야 했던 문제

직사각형의 첫 시작 좌표들로 방문여부를 체크

 

👩‍💻 코드

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

public class Main {
    static int[] arr, dx = {-1,1,0,0}, dy = {0,0,-1,1};
    static int[][] board;
    static boolean[][] visited;
    static int n, m, k, t, num, cnt, second;
    static ArrayList<Integer> list = new ArrayList<>();

    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];
        visited = new boolean[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());
        int fx = Integer.parseInt(st.nextToken());
        int fy = Integer.parseInt(st.nextToken());

        //시작 좌표를 이용해서 좌표 방문여부 판단
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(sx, sy, 0));
        visited[sx][sy] = true;

        boolean flag = false;
        out:while (!q.isEmpty()) {
            int len = q.size();
            for(int k = 0; k < len; k++) {
                Point cp = q.poll();
                if(cp.x == fx && cp.y == fy) {
                    flag = true;
                    System.out.println(cp.cnt);
                    break out;
                }
                for(int i = 0; i < 4; i++) {
                    int nx = cp.x + dx[i];
                    int ny = cp.y + dy[i];
                    if(nx<1 || ny<1 || nx>n || ny>m || visited[nx][ny]) continue;
                    //직사각형을 놓을 수 있는 위치인지 확인
                    if(nx+h > n+1 || ny+w > m+1) continue;
                    //그 위치들 중 벽이 없는지도 확인
                    if(isArrangeRectangle(nx, ny, h, w)) {
                        visited[nx][ny] = true;
                        q.offer(new Point(nx, ny, cp.cnt+1));
                    }
                }
            }
        }

        if(!flag) System.out.println(-1);

    }

    private static boolean isArrangeRectangle(int nx, int ny, int h, int w) {
        for(int i = nx; i < nx+h; i++) {
            for(int j = ny; j < ny+w; j++) {
                if(board[i][j] != 0) return false;
            }
        }
        return true;
    }

    private static class Point {
        private int x;
        private int y;
        private int cnt;

        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", cnt=" + cnt +
                    '}';
        }
    }
}