/ BOJ

BOJ_10163_색종이_JAVA

문제 : 색종이

링크 : BOJ_10163_색종이

접근 방식

색종이를 겹쳐서 놓았을 때 각 색종이의 보이는 부분의 넓이를 출력해야한다.

전체 넓이만큼의 배열을 선언하고, 색종이 번호를 1씩 증가시켜가며 해당 색종이 번호를 배열에 값으로 집어넣으면, 자동으로 값이 덮어 쓰이기 떄문에, 보이는 부분만 자연스럽게 남게된다.

풀이 방법

  1. 주어진 2차원 평면의 최대 크기가 1001이므로, 2차원배열을 1001*1001만큼으로 선언한다.

  2. 주어진 색종이의 값을 읽어와 저장하는데, 주워진 좌표값을 시작으로 각각의 범위만큼 값을 증가시켜주며 색종이 번호를 할당한다.

  3. 전체 연산횟수를 줄이고 싶어서 색종이가 들어가있는 x와 y좌표의 최댓값을 구해서 각각 xMax, yMax에 저장했다.

  4. 값을 모두 읽었다면, 카운트를 할 변수를 하나 선언하고, 색종이 개수만큼 반복한다.

  5. 각 색종이마다 xMax, yMax만큼 반복하여 2차원 배열을 탐색하며 해당 색종이 번호의 개수만큼 카운트를 더해준다.

  6. 카운트를 모두 더하면 해당 카운트를 출력하고 다음 색종이 번호로 넘어간다.

소스 코드


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

public class BOJ_10163_색종이 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		int[][] arr = new int[1001][1001];

		int N = Integer.parseInt(in.readLine());
		int xMax = 0;
		int yMax = 0;
		for(int c=1;c<=N;c++) {
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			for(int i=x;i<x+d;i++) {
				for(int j=y;j<y+r;j++){
					arr[i][j] = c;
				}
			}
			if(x+d > xMax) {
				xMax = x+d;
			}
			if(y+r > yMax) {
				yMax = y+r;
			}
		}
		for(int c=1;c<=N;c++) {
			int cnt = 0;
			for(int i=0;i<xMax;i++) {
				for(int j=0;j<yMax;j++) {
					if(arr[i][j] == c) {
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}


	}

}