[백준OJ] 16973번 직사각형 탈출 - Java

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

16973번: 직사각형 탈출

---

풀이

일반적으로 BFS를 이용하여 문제를 푸는데 주의해야할 것이 있습니다.

한 칸이 아닌 직사각형을 움직이기 때문에 직사각형 범위내에 1이 있는지를 확인해야하는데, 여까지 완전탐색을 진행한다면 Time Out이 날것입니다.

따라서 이 로직을 줄여야 하는데, 여기서 누적합을 이용하여 문제를 해결해주면 시간복잡도를 줄일 수 있습니다. 

예를들어

0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

와 같이 있으면 누적합을 이용하여

0 0 0 0 0
0 0 1 1 1
0 0 0 0 0
0 0 0 0 0

로 누적합을 구해줍니다.

 

이런 뒤 , (2,2) ~ (3,4) 까지 벽이 있는지 확인해보기 위해서는 2번째 행에서 sum[2][4] - sum[2][1] = 2 가 되기때문에 벽이 있다고 판별할 수 있게됩니다. 이를 직사각형이 걸친 모든 행을 검사하며 BFS를 수행해줍니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int answer = Integer.MAX_VALUE;
    static int N, M, H, W, SR, SC, FR, FC;
    static int[][] maze;
    static int[][] sum;

    public static class Node {
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
	
    //누적합을 이용하여 벽이 있는지 검사
    public static boolean containWall(int x, int y) {
        for (int i = x; i <= x + H - 1; i++) {
            if (sum[i][y + W - 1] - sum[i][y - 1] > 0) return true;
        }
        return false;
    }

	//갈 수 있는칸인지 검사
    public static boolean isIn(int x, int y) {
        return (1 <= x && x + H - 1 <= N && 1 <= y && y + W - 1 <= M && !containWall(x, y));
    }

    public static int bfs() {
        int[][] visited = new int[N + 1][M + 1];
        int[][] mv = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i = 1; i <= N; i++) Arrays.fill(visited[i], Integer.MAX_VALUE);

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(SR, SC));
        visited[SR][SC] = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            int cost = visited[x][y];

            if (x == FR && y == FC) {
                return cost;
            }

            for (int d = 0; d < 4; d++) {
                int nx = x + mv[d][0];
                int ny = y + mv[d][1];

                if (isIn(nx, ny) && visited[nx][ny] > cost + 1) {
                    visited[nx][ny] = cost + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.valueOf(st.nextToken());
        M = Integer.valueOf(st.nextToken());

        maze = new int[N + 1][M + 1];
        sum = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                maze[i][j] = Integer.valueOf(st.nextToken());
                sum[i][j] = maze[i][j] + sum[i][j - 1];
            }
        }

        st = new StringTokenizer(br.readLine());
        H = Integer.valueOf(st.nextToken());
        W = Integer.valueOf(st.nextToken());
        SR = Integer.valueOf(st.nextToken());
        SC = Integer.valueOf(st.nextToken());
        FR = Integer.valueOf(st.nextToken());
        FC = Integer.valueOf(st.nextToken());

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