[leetcode] 587. Erect the Fence

문제 : https://leetcode.com/problems/erect-the-fence/

Erect the Fence - LeetCode

---

볼록껍질 (Convex hull) 구하는 문제이다.
볼록껍질..! 5년 전쯤에 한 번 풀어보고 이후로 처음인거 같다.

나무들 중 반드시 정답에 포함될 수 있는 나무는 좌하단(가장 왼쪽에 있는 점들 중 가장 아래) 아니면 우상단(가장 오른쪽에 있는 점들 중 가장 위)에 있는 나무이다.
따라서 이들중 하나의 점을 기준점으로 잡고 반시계방향이나 시계방향으로 나무들을 탐색하면서 정답을 만들어간다.

이번엔 좌하단 점을 기준으로 반시계 방향으로 탐색해가며 정답을 만들어 갈 것이다.
나무들의 위치를 오름차순 정렬한 뒤 (x순 오름차순, 만일 x가 같다면 y오름차순) 가장 첫번째 점을 기준점으로 삼는다.

---

그리고 해당 기준점을 기준으로 모든 나무 위치들과의 각도를 구한다. 각도는 역탄젠트 (아크탄젠트, arctan)으로 구할 수 있다. 간단히 설명하면 tan(theta) = y/x 인데 우리가 알고있는 정보는 x, y이고 알고싶은 정보는 theta 이기 때문에 역탄젠트를 사용한 것이다. theta = arctan(y/x)
기준점에서의 각도를 구해야 하기 때문에 y-기준점.y, x-기준점.x 로 theta를 구한다.
필자는 c++로 풀었는데 Math.atan2 함수로 아크탄젠트를 구할 수 있다.

기준점을 기준으로 각도를 구했으면 앞서 말했다시피 반시계방향으로 탐색할 것이기 때문에 나무들을 각도오름차순으로 다시 정렬한다.

---

이제 나무들의 위치를 순서대로 탐색하며 정답이 불가능한 나무들은 제거하는 식으로 정답배열을 만들 것이다.
정답이 불가능한지는 어떻게 알 수 있을까. 외적을 알아야한다.
선형대수학 배운 이후 오랜만에 듣는 이름이다.

자세한 설명은 생략하고 외적의 오른손법칙에 의해 외적의 결과가 양수이면 반시계(CCW; Counter Clock Wise), 음수이면 시계방향(CW; Clock Wise)이 된다.
고등학생때 과학시간에 배운 자기장 오른손법칙이랑 비슷하다고 보면된다.

a, b 벡터의 크기는 위와 같은 수식으로 구할 수 있는데, 만일 두 벡터가 평행이라면 theta는 0이 되서 sin(0) = 0 이므로 외적의 크기는 0이된다.

ccw

a, b는 정답 배열에 있는 나무들 중 뒤에서 두 번째, 뒤에서 첫번째에 해당한다.
c 나무의 위치를 보고 b(정답배열의 가장 마지막)를 정답에 있어도 될지를 확인해야 한다.
만일 (a->b), (b->c) 벡터의 외적이 양수이거나 0인 경우 반시계방향이나 평행관계가 되어 b는 정답이 될 수 있다. 따라서 c를 정답배열에 추가하고 탐색을 이어나간다.

cw

(a->b), (b->c)의 외적결과는 음수가된다. 시계방향이므로 오목한 도형이 되어 b는 정답이 되지 못하므로 정답배열에서 뺀다 d점은 a 의 바로 전 정답배열의 요소이다. ({... d, a, b} 순으로 정답배열이 만들어져 있었음)
b를 제거했으므로 이번엔 (d->a), (a->c)의 외적결과를 구한다. 이번엔 양수가 되어 시계반대방향이므로 도형도 볼록이 되어 정답배열에 c를 넣고 탐색을 이어나간다.

---

이 때, 각도만으로 정렬을 한 뒤 위 알고리즘을 적용해서 문제를 푼다면 몇 몇 경우가 안 풀릴 것이다.

위 그림과 같이 나무가 (0,4), (2,6), (4,8), (2,2), (4,0)의 좌표에 있다고 하자.
먼저 말하자면 위와 같은 경우 정답배열엔 모든 나무가 포함된다.

처음 중점이 되는 위치는 (0,4)(let, 0번)가 될 것이다. 각도별로 정렬하면 {3, 4, 1, 2} (번호로 적으면)가 된다.
이 순서대로 탐색을 한다면 볼록껍질이 잘 만들어지다가 1, 2 나무를 세팅할 때 문제가 된다.
1번 나무를 확인할 때, 정답 배열엔 {0, 3, 4}가 들어간다. 3, 4, 1은 반시계 방향이므로 {0, 3, 4, 1}이 될 것이다.
2번 나무 확인 시, 정답 배열엔 {0, 3, 4, 1}이 들어가있다. 4, 1, 2는 시계방향이므로 1번이 제거될 것이다. 정답엔 1번 나무도 포함이 되는데 이는 옳지 않다.

따라서 나무들을 정렬할 때 중점이 되는 나무 위치와의 각도와 더불어 같은 각도를 가지는 위치들을 정렬할 또다른 기준이 필요하다.

이번 알고리즘에서 우리는 각도가 작은 순부터 나무들을 탐색하는 반시계방향 탐색을 선택했다.
따라서 각도가 같은 경우도 반시계방향으로 탐색되게 만들어주면 된다.
각도가 0이면 이는 평행이고 각도가 0보다 같거나 작은 경우는 거리가 가까운순으로 탐색되고(3, 4) 각도가 0보다 큰 경우는 거리가 먼 순으로 탐색되게(2, 1) 정렬조건을 하나 추가해준다.
해당 조건을 추가한다면 위 점들의 정렬결과는 {3, 4, 2, 1}이 되고 이 순서대로 알고리즘을 적용하면 제대로 된 정답을 구할 수 있다.

시간복잡도는 좌표들을 정렬하는데 드는 시간인 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/587.%20Erect%20the%20Fence.cpp