[BAEKJOON] 2254번 감옥건설

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

 

문제조건

 

1. 감옥의 좌표 (px,py)가 주어진다.
2. 담 기둥의 좌표들이 주어진다.
3. 감옥과 담 기둥은 일직선상에 위치할 수없다.
4. 각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다
5. 겹치지 않는 최대의 중첩된 담의 겹 수?

접근방법

 

처음보는 유형의 문제라 생각만 2시간이상하다가 검색을 통해 도움을 얻었다,,,,

역시 구현이나 어떤 알고리즘을 쓰는가 보다는 기하학적으로 접근해야하는 문제였다.

정말 오랜만에 다시 보는 벡터의 외적이 쓰인다니,,, 역시 배운게 다 쓰이긴 한다.

 

Convex Hull 알고리즘

 

이 문제에서 사용된 알고리즘이다.

convex hull이 그래서 대체 뭐냐? 2차원 좌표 평면 위에 존재하는 여러 점들 중 일부를 이용하여 모든 점을 포함하는 볼록 다각형이다. 

 

 그러면 이걸 구현하기 위해서 알고리즘이 어떻게 동작하느냐?

• 주어진 점들을 반시계방향으로 정렬하고, 정렬된 순서대로 점들을 탐색한다.
  • 반시계 방향 정렬전 기준이 되는점을 y좌표가 가장 작은 점으로 잡아준다.(minimum y-coordinate)
    • 만약 가장 작은 y좌표가 두개이상일경우에는 x좌표가 가장 작은 점
  • 반시계방향 정렬 : 기준이 되는점을 기준으로 각도(polar angle)를 오름차순으로 정렬해주는 것이다.

• stack에 첫 번째 점과 두 번째 점을 push 해준다. 그 다음 세 번째 점부터 N번째 점까지 다음의 과정을 반복한다.
• 만약 stack의 최상단에 있는 두 점을 이은 직선에 대해, 현재 탐색하는 정점이 직선의 왼쪽에 존재한다면 stack에 push한다.
• 그렇지 않다면 stack을 pop하고 위 조건을 다시 확인한다.
• 최종적으로 탐색이 끝나면 stack에는 Convex Hull을 구성하는 점들이 포함되어 있다.

CCW

CCW란? Counter Clock Wise의 약자이다.

말 그래도 반시계 방향인지 판별하는 알고리즘인데 위에 convex hull알고리즘을 수행하기위해, 벡터의 외적을 통해서 판단하려는 점이 선분의 반시계방향에 있는지 판별한다. 

이 알고리즘에 대해서는 너무 잘 정리한 글이 있어 링크를 첨부한다.

https://snowfleur.tistory.com/98

[알고리즘] CCW(Counter Clock Wise)

 

여기서 내가 주목해야 할 점은 외적을 통한 값이 양수가 나왔을때, 반시계방향이라는 것이다.

---

 

위 개념들을 전부 사용해서 문제를 풀어 봤다.

이 문제는 convex hull 알고리즘을 한번만 돌려서 사용하는 것이 아니라, 계속해서 돌려서 마침내 더 이상 감옥을 감쌀 점이 없을 때까지 이 과정을 반복해야한다는 것이다.

그리고 감옥이 볼록다각형안에 있는지 판단도 해줘야한다.

이를 위해서 나는 convex hull 알고리즘을 모두 돌리고 그 결과가 들어있는 스택에서 하나씩 pop하면서 감옥의 위치와 외적값을 비교해서 ccw가 같은지 판단해줬다. 안에 있다는 의미는 모든 선분을 기준으로 감옥과의 ccw가 같아야 한다는 말과 같다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
typedef long long ll;
using namespace std;
int n, py, px;


struct Point {
	ll x, y;
	ll p_x, p_y;
	Point(int x, int y, int p_x = 0, int p_y = 0) : x(x), y(y), p_x(p_x), p_y(p_y)
	{}
	bool operator<(Point p) {
		//원점에서부터 각도 정렬(외적)
		if(p_y * p.p_x != p_x*p.p_y) return  p_y * p.p_x < p_x * p.p_y;
		if (y != p.y) return y < p.y;
		return x < p.x;
	}
};

vector<Point> v;
ll judge(Point a, Point b, Point c) {
	ll val = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);  //벡터로 나타낸 외적
	if (val < 0) return -1;
	else if (val == 0) return 0;
	else return 1;
}

int main() {
	cin >> n >> px >> py;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back(Point(a, b));
	}
	int res = 0;
	while (1) {
		sort(v.begin(), v.end());
		//기준점 정함
		for (int i = 1; i < v.size(); i++) {
			v[i].p_x = v[i].x - v[0].x;
			v[i].p_y = v[i].y - v[0].y;
		}
		//기준점으로 부터 선분 정렬
		sort(v.begin() + 1, v.end());
		vector<Point> copy_v = v;
		stack<ll> s, copy_s;
		s.push(0);
		s.push(1);
		int nxt = 2;
		//convex hull 알고리즘
		while (nxt < v.size()) {
			while (s.size() >= 2) {
				int second = s.top();
				s.pop();
				int first = s.top();
				//외적 결과가 양수이면 반시계방향
				//ccw를 이용해서 가장바깥 볼록껍질 판단
				if (judge(v[first], v[second], v[nxt]) > 0) {
					s.push(second);
					break;
				}
			}
			s.push(nxt++);
		}
		//convex hull 알고리즘 끝
		
		//담 기둥안에 감옥이 있는지 확인
		bool pos = true;
		copy_s = s;
		int start = s.top();
		int first = s.top();
		s.pop();
		int second = s.top();
		s.pop();
		ll check = judge(v[first], v[second], Point(px, py));

		while (!s.empty()) {
			first = second;
			second = s.top();
			s.pop();
			if (check != judge(v[first], v[second], Point(px, py))) {
				pos = false;
				break;
			}
		}
		if (check != judge(v[second], v[start], Point(px, py))) pos = false;

		if (pos) {
			res++;
			set<int> se;
			for (int i = 0; i < v.size(); i++) se.insert(i);
			while (!copy_s.empty()) {
				se.erase(copy_s.top());
				copy_s.pop();
			}
			v.clear();
			for (auto i = se.begin(); i != se.end(); i++) v.push_back(copy_v[*i]);
		}
		else break;
		if (v.size() < 3) break;
	}
	cout << res;
}

 

 

소요시간은 6시간정도 소요된 것같다. 사실 처음보는 알고리즘을 마주쳐서 이해하는데 시간이 많이 걸린 것같고, 이런 문제도 있다는게 신기하고 재밌다(사실 머리가 터질거같다).

자주 보진 못하겠지만 이런 문제가 또 나온다면 이 문제가 정말많은 도움을 줄 것같다