[백준 - 16973][Gold 4] - 직사각형 탈출 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/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을 출력한다.

 

 

완전 탐색으로 풀릴까??

---

가장 쉬운 방법인 완전 탐색(BFS) 방식으로 생각해보자. 한번 갔던 곳은 다시 가지 않도록 해서 시간복잡도를 줄이는 조건을 추가하여 직사각형을 목표 좌표인 F까지 가기위한 모든 조건은 다음과 같다.

 

• 직사각형 영역에 벽이 있으면 움직이지 못한다.
• 상하좌우로 1칸씩 움직인다
• 한번 방문한 곳은 재방문하지 않는다.

 

각 조건에 따른 시간복잡도는 다음과 같다.

• 직사각형 영역에 벽이 있으면 움직이지 못한다.
  
  • 직사각형 영역에 벽이 있는지 모든 좌표를 확인한다 -> O(H*W)
• 상하좌우로 1칸씩 움직인다
  • 상하좌우 1칸씩 움직이므로 모든 칸을 돌아다니게 한다 -> O(N*M)
• 한번 방문한 곳은 재방문하지 않는다.
  • 주어진 영역의 크기만큼 배열을 만들어 방문처리를 하면 된다 -> O(1)

 

위의 조건을 바탕으로 시간 복잡도를 계산하면 다음과 같다.

 

O(N)
= (모든 좌표를 방문) * (직사각형 영역의 모든 좌표를 탐색하여 벽이 있는지 확인)
= N * M * H *W

 

이때 N과 M의 최대값은 1,000, H와 W의 최대값도 1,000이다. 그러므로 1,000^4의 연산이 발생하기 때문에 시간 제한 2초에 걸릴 수 있다. 다른 방법을 생각해야한다.

 

누적 합을 활용해서 벽이 있는지 확인해보자

---

직사각형 영역의 모든 좌표를 탐색하여 벽이 있는지 확인하는 방법을 누적합을 이용하면 O(H*W)에서 O(1)의 시간복잡도로 확실하게 줄일 수 있다! 2차원 배열의 누적합 예제 문제는 아래와 같다.

 

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

2167번: 2차원 배열의 합

 

2차원 배열 누적합의 공식에 따라 이번 문제에 적용하면 다음과 같은 식이 나온다.

 

(x1,y1) ~ (x2,y2) 영역에 있는 모든 벽의 개수
= (1,1) ~ (x2, y2) 영역에 있는 모든 벽의 개수
   - (1,1) ~ (x1-1, y2) 영역에 있는 모든 벽의 개수
   - (1,1) ~ (x2, y1-1) 영역에 있는 모든 벽의 개수
   + (1,1) ~ (x1-1, y1-1) 영역에 있는 모든 벽의 개수

영역안에 벽이 1개라도 있으면 안되기 때문에 직사각형 영역의 누적합(벽의 개수)가 1개 이상인지 확인하면 모든 좌표를 일일히 탐색할 필요 없이 바로 구할 수 있다! 위의 식을 반영한 시간복잡도를 계산하면 아래와 같다.

O(N)
= (모든 좌표를 방문) * (직사각형 영역의 모든 좌표를 누적합을 이용해 벽이 있는지 확인)
= N * M * 1
= N * M

 

이때 N과 M의 최대값은 1,000 이므로 1,000,000 연산이 발생하는데 이는 2초의 예상 연산 횟수인 2억보다 작기 때문에 제한시간 내에 해결할 수 있다!

 

해결 코드

---

 

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


public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][]map = new int[N+1][M+1];
        int[][]preSum = 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        //벽 누적합 구하기
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++) {
                preSum[i][j] = preSum[i][j-1]+preSum[i-1][j]-preSum[i-1][j-1] + map[i][j];
            }
        }

        st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int Sr = Integer.parseInt(st.nextToken());
        int Sc = Integer.parseInt(st.nextToken());
        int Fr = Integer.parseInt(st.nextToken());
        int Fc = Integer.parseInt(st.nextToken());

        Rect S = new Rect(Sr,Sc,Sr+H-1,Sc+W-1,0);

        Queue<Rect> q = new LinkedList<>();
        q.add(S);

        int[]dx = {-1,1,0,0};
        int[]dy = {0,0,-1,1};
        boolean[][] visited = new boolean[N+1][M+1];

        int min = -1;

		//BFS로 직사각형 이동
        while(!q.isEmpty()){
            Rect curr =q.poll();
            visited[curr.leftTopRow][curr.leftTopCol] = true;

            if(curr.leftTopRow == Fr && curr.leftTopCol == Fc){
                min = curr.count;
                break;
            }

            for(int i=0;i<dx.length;i++){
                Rect next = new Rect(curr.leftTopRow + dx[i]
                        ,curr.leftTopCol + dy[i]
                        ,curr.rightBottomRow + dx[i]
                        ,curr.rightBottomCol + dy[i]
                        ,curr.count+1);
				
                //맵밖으로 넘어갔으면 패스
                if(next.leftTopRow < 1 || next.rightBottomRow > N || next.leftTopCol < 1 || next.rightBottomCol > M){
                    continue;
                }
              	//이미 방문했으면 패스
                if(visited[next.leftTopRow][next.leftTopCol]){
                    continue;
                }
                //직사각형 범위에 벽이 있다면 패스
                if(getPreSum(H,W,preSum,next) > 0){
                    continue;
                }

                visited[next.leftTopRow][next.leftTopCol] = true;
                q.add(next);
            }
        }

        System.out.println(min);
    }
	
    //범위의 누적합을 구해서 벽의 개수를 알려주는 메소드
    public static int getPreSum(int H ,int W, int[][]preSum, Rect rect){
        return preSum[rect.rightBottomRow][rect.rightBottomCol]
                - preSum[rect.leftTopRow-1][rect.rightBottomCol]
                - preSum[rect.rightBottomRow][rect.leftTopCol-1]
                + preSum[rect.leftTopRow-1][rect.leftTopCol-1];
    }
}

class Rect{
    int leftTopRow;
    int leftTopCol;
    int rightBottomRow;
    int rightBottomCol;
    int count;
    public Rect(int leftTopRow, int leftTopCol,int rightBottomRow,int rightBottomCol,int count){
        this.leftTopRow = leftTopRow;
        this.leftTopCol = leftTopCol;
        this.rightBottomRow = rightBottomRow;
        this.rightBottomCol = rightBottomCol;
        this.count = count;
    }

}

 

 

실행 결과

---

 

 

팁

---

• 영역의 합을 구할 땐 2차원 배열의 누적합 공식을 이용하면 O(1) 시간복잡도로 빠르게 구할 수 있다.
• 직사각형은 왼쪽 위 좌표와 오른쪽 아래 좌표를 이용하면 쉽게 객체화할 수 있다.