백준 16973 직사각형 탈출 (Java)

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Pos {
    int y;
    int x;

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

class Pair {
    Pos pos;
    int cnt;

    public Pair(Pos pos, int cnt) {
        this.pos = pos;
        this.cnt = cnt;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());

        int[][] map = new int[n + 1][m + 1];
        boolean[][] visit = new boolean[n + 1][m + 1];

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};

        for (int i = 1; i <= n; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        tokenizer = new StringTokenizer(reader.readLine(), " ");
        int h = Integer.parseInt(tokenizer.nextToken()); // 사각형 가로 길이
        int w = Integer.parseInt(tokenizer.nextToken()); // 사각형 세로 길이
        int sr = Integer.parseInt(tokenizer.nextToken()); // 시작 위치
        int sc = Integer.parseInt(tokenizer.nextToken()); // 시작 위치
        int fr = Integer.parseInt(tokenizer.nextToken()); // 목표 위치
        int fc = Integer.parseInt(tokenizer.nextToken()); // 목표 위치

        int ans = 987654321;

        Queue<Pair> q = new ArrayDeque<>();

        q.offer(new Pair(new Pos(sr, sc), 0));
        visit[h][w] = true;

        while (!q.isEmpty()) {

            Pair cur = q.poll();

            if (cur.pos.y == fr && cur.pos.x == fc) {
                ans = Math.min(ans, cur.cnt);
            }

            for (int k = 0; k < 4; k++) {
                Pos next = new Pos(cur.pos.y + dy[k], cur.pos.x + dx[k]);
                //직사각형 범위 확인
                if (next.y <= 0 || next.x <= 0 || next.y + h - 1 > n || next.x + w - 1 > m) {
                    continue;
                }

                //방문 여부 확인
                if (visit[next.y][next.x]) {
                    continue;
                }

                //해당 직사각형 내에 벽이 있는 지 확인
                boolean valid = true;
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        if (map[next.y + i][next.x + j] == 1) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (!valid) continue;

                q.offer(new Pair(next, cur.cnt + 1));
                visit[next.y][next.x] = true;

            }

        }

        if (ans != 987654321) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }


    }
}

1. 문제

크기가 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을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ H ≤ N
• 1 ≤ W ≤ M
• 1 ≤ Sr ≤ N-H+1
• 1 ≤ Sc ≤ M-W+1
• 1 ≤ Fr ≤ N-H+1
• 1 ≤ Fc ≤ M-W+1
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

2. 풀이

기존 미로 찾는 BFS에 대상의 크기가 주어진 버전이다. 이를 토대로 문제를 풀어보자.

        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};

우선 직사각형은 상하좌우로 움직일 수 있으므로 해당 움직임에 대한 배열을 선언한다.

 class Pos {
    int y;
    int x;

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

class Pair {
    Pos pos;
    int cnt;

    public Pair(Pos pos, int cnt) {
        this.pos = pos;
        this.cnt = cnt;
    }
}

Main{

        ...
        
        boolean[][] visit = new boolean[n + 1][m + 1];

        int ans = 987654321;

        Queue<Pair> q = new ArrayDeque<>();

        q.offer(new Pair(new Pos(sr, sc), 0));
        visit[h][w] = true;

 

 큐에 넣을 Pair 클래스를 만들어 주었다. 해당 클래스에는 직사각형의 현재 위치와 시작 지점으로부터 움직임 수가 들어간다. BFS를 돌리기 위해 이를 큐에 넣고 초기화 해준다. 해당 위치의 방문 여부 배열을 선언하고 시작 위치를 추가한다.

        while (!q.isEmpty()) {

            Pair cur = q.poll();

            if (cur.pos.y == fr && cur.pos.x == fc) {
                ans = Math.min(ans, cur.cnt);
            }

            for (int k = 0; k < 4; k++) {
                Pos next = new Pos(cur.pos.y + dy[k], cur.pos.x + dx[k]);
                //직사각형 범위 확인
                if (next.y <= 0 || next.x <= 0 || next.y + h - 1 > n || next.x + w - 1 > m) {
                    continue;
                }

                //방문 여부 확인
                if (visit[next.y][next.x]) {
                    continue;
                }

                //해당 직사각형 내에 벽이 있는 지 확인
                boolean valid = true;
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        if (map[next.y + i][next.x + j] == 1) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (!valid) continue;

                q.offer(new Pair(next, cur.cnt + 1));
                visit[next.y][next.x] = true;

            }

        }

        if (ans != 987654321) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }

 BFS 파트이다. 현재 위치에서 상하좌우를 움직이는데, 격자의 범위를 벗어나지 않고, 해당 직사각형의 범위에 벽이 없어야 하므로 이를 확인한다. 위 조건까지 확인하고 해당 위치를 방문하지 않았다면 방문 표시를 해주고 이를 큐에 추가한다. 움직임 수는 현재 위치까지 오는 데의 수+1이다.

 연산이 끝나고 ans가 갱신되었다면, 즉 최소 움직임 수가 갱신되었다면 이를 출력하고, 그렇지 않다면 -1을 출력한다.