Baekjoon(백준) 1708번 - 볼록 껍질

백준 사이트의 1708번.
문제 제목 : 볼록 껍질
백준 1708

음…. 기하 문제도 좀 풀어볼 겸 예전에 영재원에서 개인 연구를 했을 때 주제가 convexhull (볼록 껍질) 이어서 이 문제를 한 번 가볍게 풀어볼려 했으나… 시간을 아주 오래 끌게 되었다.

문제 해석

convexhull 구해서 convexhull의 꼭짓점 개수가 몇 개인지 묻는 문제. 한 가지 중요한 예외사항이 있다! 바로 convexhull의 한 모서리에 3개 이상의 점이 동시에 놓여진다면 그 모서리 양 끝의 점을 빼고 나머지는 카운트 하지 말라는 것이다.

풀이 전략

하… 별것도 아닌 문제였는데 굉장히 골치 아팠던 문제였다… 혼자 디버깅해서 오류를 알아내려다 보니 시간을 너무 오래 끌었다.
기본적인 풀이 방법은 convexhull을 구하는 알고리즘 중 Graham’s Scan을 사용하는 것이다. 시간복잡도가 $O(N log_2 N)$ 이다. 그래도 나름 빠르다고 할 수 있다. 어쨌든 이 알고리즘은 인터넷이든 어디든 매우 잘 설명되어 있으니 넘어가도록 한다. 한 가지 주의할 점은 Graham’s Scan에서 ccw 방향으로 모든 점들을 정렬할 때 실제 각도를 비교하는 것이 아니라 벡터의 외적을 이용해서 정수 범위로 비교하는 것이 좋다. 물론 arctan를 이용해서 실제 각도를 구한 다음 이를 소수점 단위로 비교할 수도 있겠으나 부동 소수점 문제, 0으로 나누는 것 등등… 여러 잡음이 많은 방법이기 때문에 깔끔하게 cross product 해서 양수, 음수, 0 일 때로 판별하는 것이 가장 이상적인 방법이겠다.
가장 디버깅하느라 골치아팠던 것이 3개 이상의 점이 일직선 상에 있는 case 였는데 이는 구현에서 자세히 살펴보도록 하자.

구현

기본적으로 Graham’s Scan 알고리즘을 그대로 구현해주면 되고 3개 이상의 점이 일직선 상에 있는 경우는 이렇게 처리하면 된다. (디버깅 열심히 했는데 투자한 시간이 무색하게 방법은 너무 간단했다 ㅠ)
일단 점들을 ccw 방향으로 정렬할 때 기준점과 일직선이 되는 점이 2개 이상 나올 때 요렇게 처리해주면 된다.

long long int value = cross_product(dots[0].x, dots[0].y, a.x, a.y, b.x, b.y);
if(value > 0) return true;
else if(value < 0) return false;
else {
		if(a.y != b.y) return (a.y < b.y);
		else return (a.x < b.x);
}

ccw 방향으로 quick sort 할 때 쓰는 compare 함수인데, 자세히 보면 cross product가 0 일 때 (= 일직선 일 때) y좌표가 다르면 무조건 y좌표가 오름차순이 되도록 하고 y좌표가 같다면 x좌표가 오름차순이 되도록 하는 것을 볼 수 있다. 중요한 것은

만약 일직선이 형성된다면 y좌표를 우선적으로 오름차순으로 정렬

한다는 것이다. 그 이유는 여러 가지 예시를 그려보고 직접 시뮬레이션 해보면 더 직관적으로 다가올 것이라 생각한다. 내가 이해한대로 간단하게 말해보면 이후에 실행될 convexhull을 구하는 이 코드에서

convexhull.push(0);
convexhull.push(1);
for(int i = 2; i < N; i++) {
		//ab X ac
		int dot_a, dot_b, dot_c;
		dot_c = i;
		//if size is lower than 2 --> it means that it is straight line
		while(convexhull.size() >= 2) {
			dot_b = convexhull.top();
			convexhull.pop();
			dot_a = convexhull.top();	

			//ccw (also not straight line)
			if(cross_product(dots[dot_a].x, dots[dot_a].y, dots[dot_b].x, dots[dot_b].y, dots[dot_c].x, dots[dot_c].y) > 0) {
				convexhull.push(dot_b);
				break;				
			}	
		}

		convexhull.push(dot_c);
}

if 문을 보면 cross product가 0을 초과할 때만 점을 제거하는 작업을 중단하도록 하고 있다. 즉, cross product가 0일 때 (일직선이 형성될 때) 점을 제거하는 것도 이 코드에서 정상적으로 일어나도록 하려면, y좌표가 커지는 방향으로 정렬이 되어 있어야 한다. 왜냐하면 최종적으로 끝 점이 되는 점은 ccw의 방향을 고려할 때 y좌표가 비교적 큰 점이 되야 하고 y좌표가 같다면 x좌표가 비교적 작은 점이 되야 하기 때문이다. 사실 이렇게 백번 말로 설명하는 것보다 직접 testcase를 가지고 손으로 써가면서 시뮬레이션 해보면 감이 올 것이다.
자세한 solution 코드는 github에 있다.

baekjoon 1708 solution code