[백준]#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을 출력한다.

제한

• 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
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

예제 입력 1

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

예제 출력 1

7

예제 입력 2

6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5

예제 출력 2

8

풀이

이 문제는 BFS 알고리즘을 이용해서 풀 수 있었다. 처음엔 벽 체크를 for문을 통해서 찾았는 데 시간이 오래걸려서 HashSet을 이용해서 벽을 체크했더니 시간을 줄일 수 있었다. 하지만 메모리는 증가했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static HashSet<Pair> wall = new HashSet<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int targetX;
    static int targetY;
    static int ans=-1;
    static Iterator it;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new int[N+1][M+1];

        for(int i=1; i<=N; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
                map[i][j+1] = Integer.parseInt(input[j]);
                if(map[i][j+1]==1)
                    wall.add(new Pair(i, j+1));
            }
        }

        input = br.readLine().split(" ");
        targetX = Integer.parseInt(input[4]);
        targetY = Integer.parseInt(input[5]);
        BFS(new Rect(Integer.parseInt(input[2]), Integer.parseInt(input[2])+Integer.parseInt(input[0])-1, Integer.parseInt(input[3]), Integer.parseInt(input[3])+Integer.parseInt(input[1])-1, 0));

        System.out.println(ans);
    }

    public static void BFS(Rect rec) {
        Queue<Rect> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N+1][M+1];
        queue.add(rec);
        visited[rec.x1][rec.y1] = true;

        while(!queue.isEmpty()) {
            Rect temp = queue.poll();

            if(temp.x1==targetX && temp.y1==targetY) {
                ans = temp.cnt;
                break;
            }

            loop:for(int i=0; i<4; i++) {
                int X1 = temp.x1+dx[i];
                int X2 = temp.x2+dx[i];
                int Y1 = temp.y1+dy[i];
                int Y2 = temp.y2+dy[i];

                if(X1<1 || X2>N || Y1<1 || Y2>M || visited[X1][Y1]) continue;

                it = wall.iterator();
                while(it.hasNext()) {
                    Pair p = (Pair)it.next();

                    if(p.x>=X1 && p.x<=X2 && p.y>=Y1 && p.y<=Y2)
                        continue loop;
                }

                visited[X1][Y1] = true;
                queue.add(new Rect(X1, X2, Y1, Y2, temp.cnt+1));
            }
        }
    }

    public static class Rect {
        int x1;
        int x2;
        int y1;
        int y2;
        int cnt;

        public Rect(int x1, int x2, int y1, int y2, int cnt) {
            this.x1=x1;
            this.x2=x2;
            this.y1=y1;
            this.y2=y2;
            this.cnt=cnt;
        }
    }

    public static class Pair {
        int x;
        int y;

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