boj, 백준) 1708. 볼록 껍질 ( C / C++ )

1. 문제 링크

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

1708번: 볼록 껍질

2. 문제 개요

볼록 껍질(Convex hull)을 만드는 최소 점의 개수를 출력하는 프로그램을 작성하시오

 

3. 문제 힌트

알고리즘을 알고 있어야 한다. 간단히 설명하면, 0번점을 시작으로 2번점이 0->1을 이은 벡터의 시계 반대방향에 있는지, 시계방향에 있는지 구분하는 부분을 작성해야 한다. 다른 블로그에 알고리즘에 대한 설명이 잘 나와있으니까 코드는 아니더라고 개념만 알아보는 것을 추천합니다.

 

4. 문제 풀이

구글에 볼록 껍질 알고리즘을 찾아보면 그라함 스캔(Graham's scan) (O(nlogn))이라고 많이 알려져 있다. 그 알고리즘 자체에 대해서는 구글에 조금만 찾아보면 바로 알 수 있으므로 생략하고, 코드에 대해 한줄한줄 설명해보려고 한다.

 

 

struct Point {
	int x, y;	// 실제 위치
	int p, q;	// 기준점으로 부터 상대 위치

	Point() {}
	Point(int x_, int y_, int p_ = 0, int q_ = 0) :x(x_), y(y_), p(p_), q(q_) {}

	bool operator < (const Point &a)
	{
   		//this 가 Point a 보다 시계방향에 있다면 this가 앞에.
		if (1LL * p * a.q != 1LL*q * a.p) return 1LL * p*a.q > 1LL * q*a.p;
		if (y != a.y)	return y < a.y;	//y가 a.y보다 작으면 앞에 위치
		return x < a.x;	//x가 a.x보다 작으면 앞에 위치
	}
};

 

Point구조체를 만들어 줄 것이다.  여기서 실제 위치는 알고리즘의 첫 번째 시작인 기준점을 찾기 위해 사용될 것이다.

그리고  p, q는 그 기준점을 기준으로 벡터를 만들 때 사용될 것이다.

 

Point구조체의 생성자 부분은 넘어가고,

다음은 정렬할때 쓰이는 비교자 부분이다. 비교할 때 True를 반환한다는 것은 this의 순서가 앞에 있어야 함을 의미한다. 

 

비교자에서 첫 번째 부분은 두 벡터를 외적 했을 때, 양수가 나오면 true를 반환한다. 

(??????????)

코드에서의 우변을 좌변으로 넘겨보면 다음과 같은 식이 나온다. return 1LL * p*a.q - 1LL * q*a.p >0 ;

저 식은 두 벡터를 외적 한 값이고, 외적 한 값이 양수라면, 외적의 오른손 법칙에 의해서 반시계방향이다.

 

(외적에 있어서 오른손 법칙을 모르시는 분은 밑의 블로그 참조)

https://blog.naver.com/bloodsoda/221037155646

 

그래서 저 비교자를 호출한 this Point가 비교할 어떤 점 a와 외적 해서 양수라면 그 a점보다 반시계방향에 있다는 것이고 정렬할 때 앞에 존재해야 한다는 것을 의미한다. ( 기준점을 기준으로 반시계 방향 우선순위대로 정렬하기 때문.)

 

그 부분이 아니라면, y가 작은 순서대로 정렬하고, y가 같다면 마지막의 return 문인 x를 우선순위대로 정렬해낸다.

혹시 y < a.y인 부분이 왜 그런 건지 잘 모르시는 분들을 위해 말씀드리면 y < a.y가 true라면, y가 앞에 있어야 함을 의미한다. 즉 true를 반환하는 것은 y 가 a.y보다 작다는 것이고 작은 것이 앞에 존재하게 되므로 오름차순으로 정렬이 된다.

 

 

다음은 ccw함수를 살펴보자

long long ccw(const Point &a, const Point &b, const Point &c)
{
	//a->b벡터와 a->c의 벡터가 a->b를 기준으로 ccw인지 cw인지 체크
	return 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (c.x - a.x)*(b.y - a.y);	
}

 

두 벡터를 외적 한 결과를 반환한다. 그 값이 양수라면 a->c는 a->b의 반시계 방향에 있고 음수라면 시계방향에 존재한다.

 

다음은 main함수를 살펴보자

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		p[i] = Point(x, y);
	}
	sort(p, p + n);

	for (int i = 1; i < n; ++i)
	{
		p[i].p = p[i].x - p[0].x;
		p[i].q = p[i].y - p[0].y;
	}
	sort(p + 1, p + n);

	stack<int> s;
	s.push(0);
	s.push(1);
	int next = 2;
	while (next < n){
		while (s.size() >= 2)
		{
			int first, second;
			second = s.top();
			s.pop();
			first = s.top();
            //외적값이 양의방향이라면 오른손법칙에 의해 반시계방향
			if (ccw(p[first], p[second], p[next]) > 0)	
			{
				s.push(second);
				break;
			}
		}
		s.push(next++);
	}
	//stack에는 convex hull 정점들이 순서대로 쌓여있다.

	printf("%d", s.size());

	return 0;
}

 

점의 개수를 받고, 주어진 정점들을 조건에 맞게 정렬합니다. 사전에 정의한 비교자에 의해서 y의 좌표가 가장 작은 기준으로, y가 같다면 x가 가장 작은 기준으로 정렬됩니다. 그렇다면 배열의 0번 index에 있는 좌표가 기준점이 됩니다.

 

그 기준점을 가지고 상대 위치를 구해줍니다. (벡터)

그리고 기준점은 남겨둔 채 다른 점들을 반시계 방향 순서대로 정렬합니다.

 

stack에 확실히 convex hull이 될 0번과 1번 정점을 넣고 후보자 2번을 next에 넣어 검사합니다.

first -> second로 가는 벡터를 기준으로 next정점이 반시계 방향에 있다면 stack에 넣고 그렇지 않다면 pop을 해주는 방식으로 찾아나갑니다.

 

 

※ 저는 이 알고리즘을 공부할 때

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220857597424&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

이 블로그를 참조했습니다.

 

 

5. 실행 결과

 

지적 댓글 환영입니다 :)