백준 2669번 직사각형 4개의 합집합의 면적 구하기

< 백준 2669번 직사각형 4개의 합집합의 면적 구하기 - 마포 코딩박 >

사용한 알고리즘: ...?


 4개의 직사각형이 주어지고, 직사각형들의 합집합의 면적을 구하는 문제였습니다.
좌표 x, y 가 최대 100 이하로 주어졌기 때문에 전체 면적 (0,0) ~ (100,100) 을 전부 둘러보아 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.

(1) 각 직사각형이 차지하는 면적의 각 블록에 +1 해줍니다.

(2) (0,0) ~ (100,100) 을 둘러보며 1 이상인 블록들을 세어줍니다.
    ( 1 이상인 블록개수를 세우주므로, 중복된 블록: 2, 3... 등은 1번만 카운팅 되어 중복되어 계산 되는걸 방지할 수 있습니다. )

	#include <bits/stdc++.h>
	using namespace std;
	int graph[101][101], ans;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 0; i < 4; ++i){
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	for (int i = x1; i < x2; ++i)
	for (int j = y1; j < y2; ++j)
	graph[i][j]++;
	}
	for (int i = 0; i < 101; ++i)
	for (int j = 0; j < 101; ++j)
	if(graph[i][j]>0) ans++;
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2669.cpp hosted with ❤ by GitHub