98. Graham Scan

그레이엄의 스캔(그라함 스캔, Graham Scan)은 점 $n$개의 좌표가 주어졌을 때 $\Theta(n\text{ lg }n)$ 시간에 볼록 껍질을 찾는 알고리즘이다. 이 알고리즘은 기준점을 잡고 남은 점들을 각도 순으로 정렬한 다음 차례로 확인하는 방식으로 작동한다. 이전 글에 나온 점들의 볼록 껍질을 그레이엄의 스캔으로 구하는 과정은 다음과 같다. 이 블로그에서는 $x$좌표가 가장 작은 점, 그러한 점이 여러 개일 경우 그중 $y$좌표가 가장 작은 점을 기준점으로 했다.

$x$좌표가 가장 작은 점 $1$을 기준점으로 잡고 나머지 점들을 각도 순으로 정렬한다. 그러면 점 $6$ - 점 $8$ - 점 $4$ - 점 $2$ - 점 $7$ - 점 $5$ - 점 $9$ - 점 $3$ 순서가 된다. 이제 이 순서대로 점들을 확인하는데, 각각의 점을 확인하는 과정은 다음과 같다. 처음에 볼록 껍질을 이루는 점의 집합(이하 $S$로 표기)에는 점 $1$만이 존재한다. 현재 확인하는 점이 점 $k$일 때,

• $S$에 포함된 점이 $1$개라면 $k$를 $S$에 추가하고 다음 점으로 넘어간다.
• 그렇지 않을 경우, $S$에 가장 마지막으로 추가된 점을 $\text{A}$, $\text{A}$를 제외하고 가장 마지막으로 추가된 점을 $\text{B}$라고 하고, $\text{CCW}(\text{B}, \text{A}, k)$를 계산한다. 만약 결과가 CW인 경우 $k$를 $S$에 추가하고 다음 점으로 넘어가고, CCW 또는 평행인 경우 $A$를 $S$에서 제거한다.

이 과정을 반복하면 볼록 껍질을 구할 수 있다. 여기서는 평행한 선분이 볼록 껍질에 존재하는 경우 가운데 점들을 다 제거했는데, 전부 볼록 껍질에 포함하도록 구현하는 방법도 존재한다.

위 그림의 경우는 다음과 같다. 처음에는 $S$에 점 $1$이 존재하고, 점 $6$이 $S$에 추가된다.

점 $8$이 $S$에 추가된다.

점 $4$가 $S$에 추가된다.

점 $2$를 확인할 차례인데, $\text{CCW}(8, 4, 2)$의 결과가 CCW이므로 점 $4$가 $S$에서 제거된다. 또한 $\text{CCW}(6, 8, 2)$의 결과도 CCW이므로 점 $8$도 $S$에서 제거된다. $\text{CCW}(1, 6, 2)$의 결과는 $CW$이므로 여기서 점 $2$가 $S$에 추가된다.

점 $7$이 $S$에 추가된다.

점 $7$이 $S$에서 제거되고 점 $5$가 $S$에 추가된다.

점 $9$가 $S$에 추가된다.

점 $9$가 $S$에서 제거되고 점 $3$이 $S$에 추가된다.

모든 점을 확인했으므로 $S$에 추가된 마지막 점과 첫 번째 점을 이으면 볼록 껍질이 완성된다.

단, 점 $3$과 점 $1$을 연결하는 선분 위에 다른 점이 있을 경우 그 점이 볼록 껍질에 추가된 채로 알고리즘이 종료될 수 있기 때문에 실제로는 마지막에 점 $1$을 한번 더 확인하면서 그런 점들을 제거할 필요가 있다.

 

시간복잡도를 분석해 보면 각각의 점의 추가와 삭제가 최대 한 번만 일어나므로 $S$에 점이 추가되고 삭제되는 과정은 최대 $2n$번 발생하고, 점이 추가되거나 삭제될 때 CCW 함수가 한 번 호출된다. CCW 함수의 수행 시간이 $\Theta(1)$이므로 볼록 껍질을 구하는 과정은 $\Theta(n)$ 시간에 수행된다. 점들을 정렬하는 과정이 $\Theta(n\text{ lg }n)$ 시간에 수행되므로 전체 시간복잡도는 $\Theta(n\text{ lg }n)$이다.

 

구현은 다음과 같다. 점을 정렬해야 하므로 점의 좌표를 저장하는 구조체가 사용되었고, 점들의 각도를 기준점과의 기울기로 비교하는데 실수 연산을 피하기 위해 각각의 분모를 양변에 곱해서 계산한 것을 확인할 수 있다. 분모가 항상 양수이므로 기울기가 음수인 경우에도 정상적으로 작동한다.

#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Point{LL i, x, y;};
int s[100005];
Point p[100005];
int C1(Point a, Point b){return a.x < b.x || a.x == b.x && a.y < b.y;}
int C2(Point a, Point b){return (a.y - p[0].y) * (b.x - p[0].x) > (b.y - p[0].y) * (a.x - p[0].x);}
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3)
{
    LL t =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    if(t > 0)return 1;
    else if(t < 0)return -1;
    else return 0;
}
int main()
{
    int k, n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        p[i].i = i + 1;
        cin >> p[i].x >> p[i].y;
    }
    sort(p, p + n, C1);
    for(k = 0; p[0].x == p[k].x;)k++;
    sort(p + k, p + n, C2);
    p[n] = p[0];
    k = 0;
    for(int i = 0; i <= n;)
    {
        if(k < 2)
        {
            s[k] = i;
            i++;
            k++;
        }
        else if(ccw(p[s[k - 2]].x, p[s[k - 2]].y, p[s[k - 1]].x, p[s[k - 1]].y, p[i].x, p[i].y) < 0)
        {
            s[k] = i;
            i++;
            k++;
        }
        else k--;
    }
    k--;
    for(int i = 0; i < k; i++)s[i] = p[s[i]].i;
}

아랫부분을 이렇게 바꾸면 약간 더 간단해진다.

#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Point{LL i, x, y;};
int s[100005];
Point p[100005];
int C1(Point a, Point b){return a.x < b.x || a.x == b.x && a.y < b.y;}
int C2(Point a, Point b){return (a.y - p[0].y) * (b.x - p[0].x) > (b.y - p[0].y) * (a.x - p[0].x);}
LL ccw(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3)
{
    LL t =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
    if(t > 0)return 1;
    else if(t < 0)return -1;
    else return 0;
}
int main()
{
    int k, n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        p[i].i = i + 1;
        cin >> p[i].x >> p[i].y;
    }
    sort(p, p + n, C1);
    for(k = 0; p[0].x == p[k].x;)k++;
    sort(p + k, p + n, C2);
    p[n] = p[0];
    k = 0;
    for(int i = 0; i <= n;)
    {
        if(k < 2 || ccw(p[s[k - 2]].x, p[s[k - 2]].y, p[s[k - 1]].x, p[s[k - 1]].y, p[i].x, p[i].y) < 0)s[k++] = i++;
        else k--;
    }
    k--;
    for(int i = 0; i < k; i++)s[i] = p[s[i]].i;
}

입력되는 점들의 번호가 필요한 문제들이 존재하기 때문에 구현도 점들의 번호를 저장하는 식으로 되어 있는데, 그게 필요없다면 Point 구조체의 $i$ 멤버와 마지막 for문 등을 삭제하고 더 간단하게 구현할 수 있다.

 

그레이엄의 스캔이 볼록 껍질을 빠르게 구하는 대표적인 알고리즘으로 많이 알려져 있어서 많은 사람들이 사용하는 편인데, 실제로는 다음 글에 나오는 앤드류 알고리즘이 구현이 더 간단한 편이다.

 

[연습문제]

 

BOJ 3679. 단순 다각형 (Platinum IV)

점들을 각도 순서대로 정렬하고 출력하면 되는데, 위 코드로 정렬하면 한 변을 뒤집어 주어야 한다. 그게 어떤 변인지는 스스로 생각해 보자.