[C++][Project Euler] 코딩퀴즈 3번 - Full HD 화면상의 직사각형들이 차지하고 있는 총면적

간단한 bfs문제.

https://euler.synap.co.kr/quiz=3

입력받아야 하는 수가 좀 많아서 그렇지 bfs만 돌리면 간단하게 풀 수 있는 문제였다. 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
int display[1920][1080];
bool visited[1920][1080];

int bfs(int x, int y) {
	visited[x][y] = true;
	queue<pair<int, int>> q;
	q.push({ x, y });
	int size = 1;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= 1920 || ny >= 1080) continue;
			if (visited[nx][ny]) continue;
			if (display[nx][ny] != 1) continue;

			q.push({ nx, ny });
			visited[nx][ny] = true;
			size++;
		}
	}

	return size;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	int x1, y1, x2, y2;
	for (int i = 0; i < 1592; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++) {
			for (int y = y1; y < y2; y++) {
				display[x][y] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 1920; i++) {
		for (int j = 0; j < 1080; j++) {
			if (!visited[i][j] && display[i][j] == 1) {
				int size = bfs(i, j);
				ans += size;
			}
		}
	}

	cout << ans << endl;
	return 0;
}