[백준 3108] 로고 (C++)

문제 링크: https://www.acmicpc.net/problem/3108

3108번: 로고

1. 주의할 점

- 문제를 DFS+BFS를 이용하여 푸는 방법도 있지만, 제가 푼 방법은 범위를 비교하고 만약 서로 겹치는 점이 있다면 부모를 같게 하는 Disjoint-set 방법으로 해결했다

- 초기 상태 (0,0)에서 고개를 내리고 있으므로, (0,0)에 대한 정보를 포함시키고 시작해야한다.

 

1.5 범위 비교

- 범위 비교할때 다음과 같은 6가지의 경우만 겹치지 않는다고 판단했다

 

2. 구현

- 입력받는 모든 직사각형의 좌표를 V 벡터에 저장한다

- 모든 Node의 부모를 자기자신으로 초기화한다

- Meet(i,j) 함수를 통해 2개의 직사각형에서 겹치는 부분이 있는지 확인한다

- 겹치는 부분이 있다면, Make_union(A,B) 함수를 통해 A와 B를 합친다

- Find_par(Par[i])의 모든 값을 Set에 넣고(생각 안하고 Par[i]의 값을 Set에 넣었다가 틀렸다...), Set의 크기 -1 만큼 출력시킨다(초기 상태에 고개를 내리고 있기 때문에 1을 뺀다)

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct info {
	int x1, x2, y1, y2;
};
info tmp;
vector<info> v;
int par[1001];

int find_parent(int x) {
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a < b) par[b] = a;
	else if (a > b) par[a] = b;
}

bool meet(int i, int j) {
	info a = v[i];
	info b = v[j];
	if (b.y2 > a.y2 && a.x2 < b.x2 && a.y1 > b.y1 && b.x1 < a.x1)
		return false;
	if (a.y2 > b.y2 && b.x2 < a.x2 && b.y1 > a.y1 && b.x1 > a.x1)
		return false;
	if (b.y1 > a.y2 || b.x1 > a.x2 || a.y1 > b.y2 || b.x2 < a.x1)
		return false;
	return true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int x1, x2, y1, y2, num;
	cin >> num;
	for (int i = 0; i <= num; i++)
		par[i] = i;
	//초기에 고개를 내린상태이므로 추가해야 한다
	tmp.x1 = 0;
	tmp.x2 = 0;
	tmp.y1 = 0;
	tmp.y2 = 0;
	v.push_back(tmp);
	for (int i = 1; i <= num; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		tmp.x1 = x1;
		tmp.x2 = x2;
		tmp.y1 = y1;
		tmp.y2 = y2;
		v.push_back(tmp);
	}
	for (int i = 0; i < num; i++) {
		for (int j = i + 1; j <= num; j++) {
			if (meet(i, j)) 
				make_union(i, j);		
		}
	}
	set<int> s;
	for (int i = 0; i <= num; i++)
		s.insert(find_parent(par[i]));
	cout << s.size() - 1;
	system("pause");
	return 0;
}