[C/C++] 백준 - 2669번 : 직사각형 네개의 합집합의 면적 구하기

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

2669번: 직사각형 네개의 합집합의 면적 구하기

문제

평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭짓점이 겹칠 수도 있다.

이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오.

입력

입력은 네 줄이며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어진다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭짓점의 x좌표, y좌표이고 세 번째와 네 번째의 정수는 사각형의 오른쪽 위 꼭짓점의 x좌표, y좌표이다. 모든 x좌표와 y좌표는 1이상이고 100이하인 정수이다.

출력

첫 줄에 네개의 직사각형이 차지하는 면적을 출력한다.

 

그림이 있어서 어려워보이지만 문제를 읽어보면 쉬운 문제이다.

4개의 사각형이 주어지고 그 사각형들이 이루는 면적을 구하면 되는 문제인데, 각 사각형의 모든 좌표가 주어지는 것이 아닌 왼쪽 아래 좌표와 오른쪽 위 좌표 2개만 주어진다.

 

처음에는 문제를 어떻게 해결할지 생각하다 하나 입력 받을 때마다 전에 입력했던 사각형과 겹치는 부분이 있는지 확인하고, 있으면 겹치는 부분의 넓이만 빼는 방식으로 하려했다. 하지만 이렇게 하다보면 3번째 4번째 사각형을 입력했을 때 전 사각형 뿐만 아니라 그 전 사각형과 겹치는 부분도 알아야하기 때문에 더 복잡해질거 같았다. 그래서 이 풀이는 아닐거라고 생각하고, 그냥 단순히 쉽게 구현해보자 라는 생각으로 2차원 배열을 만들고, 아직 색칠 되어있지 않으면 색칠하고, 색칠이 되어있으면 건너띄는 방식으로 구현했더니 쉽게 맞을 수 있었다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/2669

int adj[101][101]; int cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 1; i <= 4; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		for (int y = b; y < d; y++) {
			for (int x = a; x < c; x++) {
				if (!adj[y][x]) {
					cnt++;
					adj[y][x] = 1;
				}
			}
		}

	}
	cout << cnt << endl;
	
	return 0;
}