[백준/BOJ] 10000 원 영역 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/10000

[설명]
원이 하나씩 생길 때 전체가 나누어지는 수는 1 또는 2씩 증가하게 된다. 2씩 증가하는 경우는 작은 원이 인접하면서 더 큰 원의 양 끝을 채울 때이다.

원의 왼쪽 끝 좌표와 오른쪽 끝 좌표에 대하여 왼쪽 끝이 작은 것이 먼저, 같다면 오른쪽 끝이 큰 것이 먼저 오도록 정렬한다. 이후 원의 왼쪽, 오른쪽 끝 좌표를 unordered_map에 넣어줄 것이다. 집어넣는 방식은 두 좌표 모두 없다면 index를 넣고 하나만 있다면 그 좌표에 적힌 값을 넣어준다. 둘 다 있을 때 두 값이 같다면 양 끝을 채운게 되므로 1을 더 더해준다.

처음 정렬한 방식을 생각해보면 위 풀이가 적절함을 알 수 있다. 가능한 왼쪽 끝의 좌표가 작은 원부터 처리하므로 이후 등장하는 원은 내부에 있을 때(접할 수도 있음), 외부에서 접할 때, 혹은 떨어져 있는 경우로 나뉘게 된다. 외부에서 접하면 이를 이어서 생각해 더 큰 원의 양쪽 끝을 인접한 원으로 이을 수 있는지 판단할 수 있고 떨어져 있다면 그렇지 않다고 판단할 수 있다. 만약 내부에 있다면 위를 반복적으로 고려한 것이 된다.

[코드]

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

struct info {
	int O, R;
};

bool cmp(const info& a, const info& b) {
	if (a.O - a.R < b.O - b.R) return 1;
	else if (a.O - a.R == b.O - b.R && a.R > b.R) return 1;
	return 0;
}

info arr[300001];
unordered_map<int, int> parent;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, i, ans = 1; cin >> n;
	for (i = 1; i <= n; i++) cin >> arr[i].O >> arr[i].R;
	sort(arr + 1, arr + n + 1, cmp);
	for (i = 1; i <= n; i++) {
		ans++;
		if (!parent.count(arr[i].O - arr[i].R) && !parent.count(arr[i].O + arr[i].R)) {
			parent[arr[i].O - arr[i].R] = i;
			parent[arr[i].O + arr[i].R] = i;
		}
		else if (!parent.count(arr[i].O - arr[i].R) && parent.count(arr[i].O + arr[i].R)) {
			parent[arr[i].O - arr[i].R] = parent[arr[i].O + arr[i].R];
		}
		else if (parent.count(arr[i].O - arr[i].R) && !parent.count(arr[i].O + arr[i].R)) {
			parent[arr[i].O + arr[i].R] = parent[arr[i].O - arr[i].R];
		}
		else if (parent[arr[i].O - arr[i].R] == parent[arr[i].O + arr[i].R]) {
			ans++;
		}
		else if (parent[arr[i].O - arr[i].R] != parent[arr[i].O + arr[i].R]) {
			parent[arr[i].O - arr[i].R] = parent[arr[i].O + arr[i].R];
		}
	}
	cout << ans;
}