[백준] 10163번: 색종이 Java

문제

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

그림 - 1

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

그림 - 2

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

 

입력

입력의 첫 번째 줄에는 색종이의 장수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 이어서 N장의 색종이에 관한 입력이 각 색종이마다 한 줄씩 차례로 주어진다. 색종이가 놓이는 평면은 가로 최대 1001칸, 세로 최대 1001칸으로 구성된 격자 모양이다. 격자의 각 칸은 가로, 세로 길이가 1인 면적이 1인 정사각형이다.

편의상 가로 6칸, 세로 6칸으로 이루어진 격자의 예를 들어 설명하면, 각 칸에 표시된 값 (a,b)는 해당 칸의 번호를 나타낸다. 가장 왼쪽 아래의 칸은 (0,0) 가장 오른 쪽 위의 칸은 (5,5)이다. 

그림 - 3

색종이가 놓인 상태는 가장 왼쪽 아래 칸의 번호와 너비, 높이를 나타내는 네 정수로 표현한다. 예를 들어, 위 그림에서 회색으로 표시된 색종이는 (1,4)가 가장 왼쪽 아래에 있고 너비 3, 높이 2이므로 1 4 3 2로 표현한다. 색종이가 격자 경계 밖으로 나가는 경우는 없다. 

출력

입력에서 주어진 순서에 따라 N장의 색종이를 평면에 놓았을 때, 입력에서 주어진 순서대로 각 색종이가 보이는 부분의 면적을 한 줄에 하나씩 하나의 정수로 출력한다. 만약 색종이가 보이지 않는다면 정수 0을 출력한다. 

접근

색종이가 펼쳐지는 평면은 가로 길이, 세로 길이가 1001이다.

색종이마다 번호를 지정하고, 평면 배열에 색종이가 놓이는 공간에 해당 번호를 지정한다.

나중에 오는 색종이는 이미 번호가 있더라도 나중 색종이의 번호가 덮여지게 된다.

모든 색종이를 평면에 표시하였으면,

완전탐색을 통해 색종이 번호가 각각 몇개 있는지를 파악한다.

 

그림 - 3의 경우, 기존 배열이라 생각하는 상하와 행과 열이 바뀌어 있지만 당황하지 말고, 주어진 자료를 잘 활용한다.

(열, 행, 너비, 높이)

 

구현

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

public class Main {
	//https://www.acmicpc.net/problem/10163
	
	static final int INF = 1001;
	static int[][] Board = new int[INF][INF];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//종이 개수
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		//종이는 1번부터 시작
		for(int i=1;i<=n;i++) {
			st=new StringTokenizer(br.readLine());
			//열
			int c=Integer.parseInt(st.nextToken());
			//행
			int r=Integer.parseInt(st.nextToken());
			//너비
			int w=Integer.parseInt(st.nextToken());
			//높이
			int h=Integer.parseInt(st.nextToken());
			//구역에 해당 종이 번호 입력
			for(int j=0;j<h;j++) {
				for(int k=0;k<w;k++) {
					Board[r+j][c+k]=i;
				}
			}
		}
		//답 출력을 위한 배열 선언
		int[] answer = new int[n+1];
		//완전 탐색
		for(int i=0;i<INF;i++) {
			for(int j=0;j<INF;j++) {
				//해당 번호 증가
				answer[Board[i][j]]++;
			}
		}
		//출력, 1번부터 종이 / 0은 빈공간
		for(int i=1;i<=n;i++) {
			bw.append(answer[i]+"\n");
		}
		
		bw.close();
		br.close();
	}
}