[Java] Boj 1531: 투명

문제

세준이는 1×1크기의 그림으로 모자이크한 100×100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 불투명한 종이로 가린다고 항상 그 그림이 안 보이는 것은 아니다. 그 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면 그림은 그 부분에서 보이게 된다.

그림의 크기는 100×100이고, N개의 종이는 왼쪽 아래 모서리 좌표와 오른쪽 위 모서리 좌표가 입력으로 들어온다. 또, 종이가 가리는 영역에는 두 모서리의 좌표도 포함된다. 예를 들어, (1,1)부터 (2,2)를 가린다면, 총 4개의 그림이 가려진다. (1,1), (1,2), (2,1), (2,2).

100×100크기의 모자이크 중에 보이지 않는 그림의 개수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌표, 오른쪽 위 모서리의 x, y좌표 순으로 주어진다. 모든 좌표는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 출력한다.

---

풀이

그리 어렵지 않은 구현 문제로 100 * 100 크기의 2차원 배열을 만들고, 입력받은 좌하단 모서리 좌표와 우상단 모서리 좌표를 통해 해당 구간의 값을 1씩 증가시킨다. 

( (1, 1) (3, 3)을 입력받으면 arr[1][1], arr[1][2], arr[1][3], arr[2][1], ..., arr[3][3]의 값을 1 증가시키는 형태)

입력받는 모서리들의 좌표를 기반으로 해당 구간의 배열 값을 1씩 증가시키고, 마지막으로 100 * 100 배열의 값이 M보다 큰 값이 크다면 cnt 값을 증가시켜 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[][] arr = new int [101][101];
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(bf.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            for (int x = x1; x <= x2; x++) {
                for (int y = y1; y <= y2; y++) {
                    arr[x][y]++;
                }
            }
        }
        int cnt = 0;
        for (int i=1; i<101; i++) {
            for (int j=1; j<101; j++) {
                if (arr[i][j] > m) cnt++;
            }
        }
        System.out.println(cnt);
    }
}