[Day 3] BOJ 22942 : 데이터 체커

khj20006·2022년 11월 2일

기하학 스위핑 스택

100 Day Algorithm Challenge

목록 보기

3/6

문제

https://www.acmicpc.net/problem/22942

중심이 $x$ 축 위에 있는 원 $N$ 개 주어졌을 때 이 원들 중 서로 교차하는 부분이 있는지 확인하는 문제입니다.

해결 전략

두 개의 원 교차 판별

이 문제의 핵심은 모든 원의 중심이 $x$ 축위에 있고, 정수 좌표를 갖는다는 것입니다.

임의의 원 두 개가 있다고 가정해봅시다.
아래 그림과 같이 3가지의 경우가 나올 수 있습니다.
그림에서, 연두색 원을 $A$ , 파란색 원을 $B$ 로 정하겠습니다.

만나지 않는 경우 1

한 원이 다른 원을 포함하는 경우이고, $a_1 \lt b_1 \lt b_2 \lt a_2$ 와 동치입니다.

만나지 않는 경우 2 (포함하지 않음)

포함관계가 없는 두 원의 경우이고, $a_1 \lt a_2 \lt b_1 \lt b_2$ 와 동치입니다.

만나는 경우

교점이 생기는 경우이고, $a_1 \le b_1 \le a_2 \le b_2$ 와 동치입니다.

이제 원의 양 끝점에서의 대소를 비교하는 것으로 교차 판별을 할 수 있게 되었습니다.

따라서 입력받는 중심 $x$ 와 반지름 $r$ 을 이용해,
원의 데이터를 { $x-r, x+r$ } 형태로 저장해둡시다.

두 개 있을 때는 비교할 수 있지만, N개의 원이 있을 때는..?

스위핑 기법

먼저, 스위핑 기법에 대하여 알아봅시다.

스위핑 기법이란, 정렬된 데이터들을 한 쪽 끝에서부터 반대쪽으로 훑어가는 기법입니다.

이 문제를 예로 설명 드리면,
왼쪽 가장 끝 원에서 시작하여 다음 원으로 이동하면서 교차 판별을 하면 모든 원에 대한 판별이 가능해집니다.

구현

스위핑 기법을 사용하기 위해 원들을 오름차순 정렬합니다.
이렇게 정렬된 $N$ 개의 원들을 왼쪽에서부터 $A_0, A_1, A_2, ... , A_{N-1}$ 라고 합시다.

원들의 포함 관계를 유지하기 위해 스택(stack) 자료구조를 사용합니다.
스택에 $A_0$ 를 삽입하고, $1 \le i \le N-1$ 인 $i$ 에 대해 원 $A_i$ 와 스택의 Top에 있는 원을 비교합니다.

한 원이 다른 원을 포함하면, 안쪽 원을 스택에 삽입합니다.
-> 스택의 Top에는 가장 안쪽 원, Bottom에는 가장 바깥쪽 원이 저장됩니다.
포함 관계가 없고 서로 교차하지 않는다면,
스택이 비거나 스택의 Top과 포함관계가 생길 때까지 Pop을 합니다.
Pop작업이 끝나면 현재의 원을 스택에 삽입합니다.
교차하면 반복문을 탈출하고 "NO"를 출력해주면 됩니다.

코드

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, a, b;
	cin >> N;
	pair<int, int> circle[200000]{};
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		circle[i] = { a - b,a + b };
	}
	sort(circle, circle + N);

	bool success = 1;
	stack<pair<int, int>> S;
	S.push(circle[0]);
	for (int i = 1; i < N; i++) {
		pair<int, int> now = circle[i];
		if (now.second < S.top().second)
			S.push(now);
		else if (now.first > S.top().second) {
			while (!S.empty() && now.first > S.top().second)
				S.pop();
			if (S.empty() || now.second < S.top().second)
				S.push(now);
			else {
				success = 0;
				break;
			}
		}
		else {
			success = 0;
			break;
		}
	}

	cout << (success ? "YES" : "NO");
}