์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๊ฒน์น˜๋Š” ์‚ฌ๊ฐํ˜•์„ ๊ฐ๊ธฐ ๋‹ค๋ฅธ ์ง‘ํ•ฉ์œผ๋กœ ๋ถ„๋ฅ˜ + (0,0) ์ ์ด ์†ํ•˜๋Š” ์ง‘ํ•ฉ์ด ์žˆ๋Š”์ง€ ํ™•์ธ
  • ์•ž์—์„œ๋ถ€ํ„ฐ ๊ฒน์น˜๋Š” ์‚ฌ๊ฐํ˜•์„ ํ™•์ธํ•˜๊ณ , ๊ฒน์น˜๋ฉด, ํ์˜ ๋งจ ์•ž์— ๋„ฃ์–ด์„œ DFS ๋ฐฉ์‹์œผ๋กœ ์ง‘ํ•ฉ์„ ๋ถ„๋ฅ˜
  • ๋งค๋ฒˆ ๋ชจ๋“  ์‚ฌ๊ฐํ˜•์„ ๊ฒ€์‚ฌํ•˜๋Š”๋ฐ, ์ด๋ฏธ ๋ถ„๋ฅ˜๋œ ์‚ฌ๊ฐํ˜•์€ ๋‹ค์‹œ ๊ฒ€์‚ฌํ•˜์ง€ ์•Š์•„๋„ ๋จ.
  • ์ด๋•Œ (0,0,0,0)์ธ ์‚ฌ๊ฐํ˜•(์‚ฌ์‹ค์€ ์ )์„ 1๊ฐœ ๋” ์ €์žฅํ•˜์—ฌ, ๊ฒ€์‚ฌํ• ๋•Œ ์ด ์ ๋„ ๊ฒ€์‚ฌํ•˜๋„๋ก ํ•˜์—ฌ, ํด๋ž˜์Šค๊ฐ€ ๋ถ„๋ฅ˜๋˜๋ฉด, ์›์ ์ด ์†ํ•˜๋Š” ์ง‘ํ•ฉ์ด ์žˆ๋Š”๊ฑฐ๊ณ , ๋ถ„๋ฅ˜๋˜์ง€ ์•Š์œผ๋ฉด ์—†๋Š” ๊ฒƒ์ด๋‹ˆ, ์ด๊ฒƒ์œผ๋กœ ์ตœ์ข… ๊ฒฐ๊ณผ๋ฅผ ๊ณ„์‚ฐํ•จ.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <list>
using namespace std;
 
int N, point[1001][4], classes[1001], classCount;
bool check[1000];
list<int> q;
 
void classify();
void countClass();
 
int main() {
	memset(classes, -1, sizeof(classes));
 
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> point[i][0] >> point[i][1] >> point[i][2] >> point[i][3];
 
	classify();
	countClass();
 
	for (int i = 0; i < N + 1; i++) {
		cout << classes[i] << " ";
	}
	cout << endl;
 
	if (classes[N] == -1)
		cout << classCount;
	else
		cout << classCount - 1;
}
 
void classify() {
	int nextClass = 0;
 
	for (int i = 0; i < N; i++)
		q.push_back(i);
 
	while(!q.empty()) {
		int i = q.front();
		q.pop_front();
 
		if (classes[i] == -1)
			classes[i] = nextClass++;
 
		int x1 = point[i][0], x2 = point[i][2], y1 = point[i][1], y2 = point[i][3];
		int iline[4][4] = { {x1, y2, x2, y2}, {x2, y1, x2, y2},{x1, y1, x2, y1},{x1, y1, x1, y2} }; // ์œ„ ์˜ค ์•„ ์™ผ
 
		for (int j = 0; j < N + 1; j++) {
			if (classes[j] != -1)
				continue;
			bool same = false;
 
			x1 = point[j][0], x2 = point[j][2], y1 = point[j][1], y2 = point[j][3];
			int jline[4][4] = { {x1, y2, x2, y2}, {x2, y1, x2, y2},{x1, y1, x2, y1},{x1, y1, x1, y2} };
 
			for (int k = 0; k < 4; k++) {
				for (int p = 0; p < 4; p++) {
					if (k % 2 == 0 && p % 2 == 0 && iline[k][1] == jline[p][1] && !(iline[k][0] > jline[p][2] || iline[k][2] < jline[p][0]))
						same = true;
					else if (k % 2 == 1 && p % 2 == 1 && iline[k][0] == jline[p][0] && (!(iline[k][1] > jline[p][3] || iline[k][3] < jline[p][1])))
						same = true;
					else if (k % 2 == 0 && !(iline[k][0] > jline[p][0] || iline[k][2] < jline[p][0] || iline[k][1] > jline[p][3] || iline[k][1] < jline[p][1]))
						same = true;
					else if (!(iline[k][0] > jline[p][2] || iline[k][0] < jline[p][0] || iline[k][1] > jline[p][3] || iline[k][3] < jline[p][1]))
						same = true;
				}
			}
			if (same) {
				classes[j] = classes[i];
				q.push_front(j);
			}
		}
	}
}
 
void countClass() {
	for (int i = 0; i < N; i++) {
		if (!check[classes[i]]) {
			check[classes[i]] = true;
			classCount++;
		}
	}
}