백준 14846번 <직사각형과 쿼리>

백준 알고리즘 14846번

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

14846번: 직사각형과 쿼리

---

14846번

N행 N열로 이루어진 정사각형 행렬 A가 주어진다. 이때, 쿼리를 수행하는 프로그램을 작성하시오.

• x1 y1 x2 y2: 왼쪽 윗칸이 (x1, y1)이고, 오른쪽 아랫칸이 (x2, y2)인 부분 행렬에 포함되어 있는 서로 다른 정수의 개수를 출력한다.

---

문제 해결

누적합을 이용해서 문제를 풀었다.

 

행렬 A가 있다고 할 때, 누적 숫자의 개수를 담은 check 배열을 만들었다.

check[i][j] = (i, j) 좌표를 사각형의 오른쪽 아래라고 생각했을 때, 그 사각형에 포함된 숫자의 개수를 가진 배열

위의 그림과 같이 check[1][1]의 배열을 구할 수 있고, 위의 행렬에 대해 모두 구했을 때는 아래와 같다.

 

누적합인 check 배열을 구하는 방법은 다음과 같다.

• check[0][0]은 a[0][0]만 1인 int 형 배열이다.
• check[i][0]은 check[i-1][0]에서 a[i][0]번째 값에 +1을 한다.
• check[0][j]은 check[0][j-1]에서 a[0][j]번째 값에 +1을 한다.
• check[i][j]는 check[i][j-1]의 값에 각각 check[i-1][j]의 값을 더하고 check[i-1][j-1]의 값을 빼준다.

 

x1, y1, x2, y2 연산을 하는 방법은 다음과 같다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_14846 {
    static int N;
    static int[][] input;
    static int[][][] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        input = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] inArr = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                input[i][j] = Integer.parseInt(inArr[j]);
            }
        }

        // check[i][j] : (i, j)까지 누적 숫자의 개수
        check = new int[N][N][11];
        check[0][0][input[0][0]] = 1;
        for (int i = 1; i < N; i++) {
            check[i][0] = deepcopy(check[i - 1][0]);
            check[i][0][input[i][0]] ++;
            check[0][i] = deepcopy(check[0][i-1]);
            check[0][i][input[0][i]] ++;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                check[i][j] = minus(plus(check[i-1][j], check[i][j-1]), check[i-1][j-1]);
                check[i][j][input[i][j]]++;
            }
        }

        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String[] inArr = br.readLine().split(" ");
            int x1 = Integer.parseInt(inArr[0]) - 1;
            int y1 = Integer.parseInt(inArr[1]) - 1;
            int x2 = Integer.parseInt(inArr[2]) - 1;
            int y2 = Integer.parseInt(inArr[3]) - 1;
            int[] answer = check[x2][y2];
            if (x1 - 1 >= 0) {
                answer = minus(answer, check[x1 - 1][y2]);
            }
            if (y1 - 1 >= 0) {
                answer = minus(answer, check[x2][y1 - 1]);
            }
            if (x1 - 1 >= 0 && y1 - 1 >= 0) {
                answer = plus(answer, check[x1 - 1][y1 - 1]);
            }
            sb.append(count(answer)).append("\n");
        }
        System.out.println(sb);
    }

    static int count(int[] arr) {
        int cnt = 0;
        for (int i = 0; i < 11; i++) {
            if (arr[i] > 0) {
                cnt++;
            }
        }
        return cnt;
    }

    static int[] deepcopy(int[] arr) {
        int[] copy = new int[11];
        for (int i = 0; i < 11; i++) {
            copy[i] = arr[i];
        }
        return copy;
    }

    static int[] plus(int[] a, int[] b) {
        int[] arr = new int[11];
        for (int i = 0; i < 11; i++) {
            arr[i] = a[i] + b[i];
        }
        return arr;
    }
    static int[] minus(int[] a, int[] b) {
        int[] arr = new int[11];
        for (int i = 0; i < 11; i++) {
            arr[i] = a[i] - b[i];
        }
        return arr;
    }
}

---

결과

 

---