백준 10163번: 색종이

문제 설명

• 각 도형이 최종적으로 보여지는 넓이를 구하는 문제입니다.

접근법

• 격자 크기만큼의 2차원 배열을 만듭니다.
• 색종이를 붙이는 순서를 활용합니다.
• 색종이가 붙여진 칸을 해당 색종이 순서로 바꿉니다.
• (x,y)에 1번 색종이가 붙여진 상태에서 나중에 5번 색종이가 (x,y)에 붙여지면 (x,y)의 값이 1에서 5로 바뀌면서 1번 색종이의 넓이가 1 줄어듭니다.
• 2차원 배열에서 1~N의 개수가 각 색종이의 넓이를 나타냅니다.

정답

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		int[] answer = new int[N+2];


		int[][] board = new int[1001][1001];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = x1 + Integer.parseInt(st.nextToken());
			int y2 = y1 + Integer.parseInt(st.nextToken());
			for (int j = x1; j < x2; j++) {
				for (int j2 = y1; j2 < y2; j2++) {
					board[j][j2] = i+1;
				}
			}
		}
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				if(board[i][j] == 0) continue;
				answer[board[i][j]+1] ++;
			}
		}
		
		for (int i = 2; i < N+2; i++) {
			System.out.println(answer[i]);
		}
	}

}

기타

• 이번 색종이 문제도 정석적이지 않은 방법으로 접근하기 시작하면 정답에 도달하기 어려워 집니다.
• 시간복잡도를 생각해 보면 좋을 거 같은 문제입니다. 1000x1000 2차원 배열을 전부 고려하는게 비효율적으로 보일 수 있지만 3중반복문이 아니라 2중반복문을 2번 사용하기 때문에 1000x1000x2, 결국 O(N^2)이 소요되는 문제입니다.

처음 접근법

• 새로 종이가 추가될 때마다 이전 종이들과의 겹쳐진 부분을 확인해서 겹쳐져 있으면 너비를 빼는 방식으로 접근했고, 시간초과로 부분점수만 획득했습니다.