백준 - 10163번(색종이)

문제 출처: https://www.acmicpc.net/problem/10163

---

문제

• 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.

그림-1

• 여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.

그림-2

• N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분의 면적을 구하는 프로그램을 작성하시오.

---

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());

        StringBuilder sb = new StringBuilder();

        int[][] paper = new int[1001][1001];
        int[] count = new int[N + 1];

        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int col = Integer.parseInt(tokenizer.nextToken());
            int row = Integer.parseInt(tokenizer.nextToken());
            int width = Integer.parseInt(tokenizer.nextToken());
            int height = Integer.parseInt(tokenizer.nextToken());

            for (int j = row; j < row + height; j++) {
                for (int k = col; k < col + width; k++) {
                    paper[j][k] = i + 1;
                }
            }
        }

        for (int i = 0; i < 1001; i++) {
            for (int j = 0; j < 1001; j++) {
                count[paper[i][j]]++;
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(count[i]).append("\n");
        }

        System.out.println(sb);
    }

}

---

• 최대 크기인 1001 * 1001 크기의 배열을 선언한다.
• 들어오는 색종이에 따라 1씩 증가시키며 색종이의 영역을 숫자로 채운다.
• 마지막에 전체 배열을 탐색하며 각 색종이가 보이는 영역의 숫자를 카운트하여 정답을 도출한다.