[백준 2563] 색종이

https://www.acmicpc.net/problem/2563

2563번: 색종이

---

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

<그림>

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

풀이

이 문제의 핵심은 검은색 색종이를 붙이는데 중복되는 부분을 어떻게 처리할지다. 제일 간단하게 하는 방법은 도화지의 가로, 세로의 크기만큼 2차원 배열을 만들어서 0으로 초기화한 후, 검은색 색종이를 붙이는 부분을 1로 변경해서 2차원 배열의 1의 값을 세는 방법이다. 이 방식을 사용하면 이미 검은색 색종이를 붙인 부분을 쉽게 해결할 수 있다.

코드

C++

# include <iostream>

using namespace std;

// 2차원 배열 선언 (도화지)
bool arr[100][100];

int main() {
	// 검은색 색종이 개수 변수 선언, 검은색 색종이를 붙인 넓이를 저장할 변수 선언
	int n, total_area = 0;
	cin >> n;
	int count = 0;
	while (true) {
		int x, y;
		cin >> x >> y;
		// 검은색 색종이를 붙인 범위
		for (int i = x; i < x + 10; i++) {
			for (int j = y; j < y + 10; j++) {
				// 현재 위치가 검은색 색종이가 붙어있지 않을 경우에만
				if (!arr[i][j]) {
					total_area++;
					arr[i][j] = 1;
				}
			}
		}
		count++;
		// 검은색 색종이를 다 붙이면 while문 탈출
		if (count == n)
			break;
	}
	// 검은색 색종이의 총 넓이 출력
	cout << total_area;
}

2차원 배열은 검은색 색종이를 붙이지 않은 0과 붙인 1만 있으면 되기 때문에 bool형으로 선언했다. 또한, 전역변수로 선언했기 때문에 직접 초기화를 하지 않아도 0으로 초기화가 된다.

x, y 좌표로 현재위치에 검은색 색종이가 붙어 있지 않은 경우만 체크하기 때문에 중복을 해결할 수 있다.