점 잇기 문제 (SCPC 4회 본선 3번: 기판)

2차원 평면에 검은 점과 하얀 점이 각각 N개씩 찍혀 있다. (으레 기하 문제가 그렇듯 임의의 세 점이 한 직선 위에 있지는 않다고 치자)

이제 우리는 각각의 검은 점에 하얀 점 하나씩을 선분으로 이어 주려고 한다. 단, 선분끼리 교차하지 않아야 한다.

총 N개의 선분을 그어 모든 하얀 점과 검은 점들을 이어줄 수 있을까?

N=6인 경우 점 잇기 예시

 

대충 이어보면 생각보다 잘 이어지긴 한다. 하지만 모든 점들을 이어주는 것이 항상 가능할까?

예를 들어서 N = 10만 정도이고 검은 점과 하얀 점이 복잡하게 얽혀 있는 경우에도 가능할까?

 

결론을 먼저 말하면 가능하다. 이를 증명하는 방법은 여러 가지가 있는데, 이 중 매우 깔끔하면서 재미있는 방법을 하나 소개한다.

많은 내용의 출처는 SW Expert Academy - Learn - Course - Programming Professional - 증명의 중요성 - 8차시이다.

 

일단 교차하지 않아야 한다는 조건은 잠시 무시하고, 교차하든 말든 그냥 이어준다고 해 보자.

이러면 경우의 수가 얼마나 나올까? 점을 이어주는 방법이 총 N!가지가 있음을 쉽게 알 수 있다.

이를 모두 나열해보았다고 치자.

총 N!의 케이스 중에서는 선분이 겹치는 경우도 있고, 아닌 경우도 있을 것이다.

이 때, 뜬금없지만, 각각의 경우에서 "선분의 길이의 합"에 집중을 해 보자.

총 N!의 경우에서 각각의 경우의 선분의 길이의 합을 구했다 치자.

당연하게도 이 중 선분의 길이의 합이 가장 작은 경우가 존재할 것이다.

 

여기서 핵심이 나온다.

선분의 길이의 합이 가장 작은 경우에는 교차하는 두 선분이 존재하지 않는다!

만약 선분의 길이의 합이 가장 작은 케이스에, 교차하는 두 선분이 존재한다고 가정해보자.

이 경우 교차하는 두 선분을 서로 풀어주면 거리의 합이 감소된다. 따라서 선분의 길이의 합이 가장 작은 케이스라는 가정에 모순이다.

 

따라서 선분이 교차하지 않도록 총 N개 쌍의 점을 이어주는 방법은 항상 존재한다.

 

이 방법을 사용하여, 이어주는 방법 또한 찾아낼 수 있다.

일단 N개 쌍을 랜덤하게 이어준 뒤, 더 이상 교차하는 선분이 없을 때까지 교차하는 두 선분을 찾아 풀어주는 것만으로 답을 찾을 수 있다.

교차를 풀어줄 때마다 전체 선분의 길이의 합은 감소하므로, 이 방법이 수렴함(즉, 무한루프에 빠지지 않음) 또한 자명하다.

 

풀어볼 수 있는 문제로는 JUNGOL 사이트 2392번 선 잇기가 있다.

사이트가 영 상태가 좋지 않아서, 답이 여럿일 경우 아무것이나 출력하라고 되어있는데 스페셜 저지가 없어서 제대로 된 채점이 안 되고 있으므로 풀어보지는 말기를 추천한다.

 

이 방법은 쉽고 간편하기는 하지만 충분히 빨리 동작하지 않는다.

조금 더 현실적인 시간 복잡도에서 작동하는 알고리즘을 생각해보자.

이 방법 또한 엄청나게 아름다우므로 꼭 읽어보기를 바란다.

 

조금 더 빠르게 점 잇기

위 방법과는 조금 다른 접근법으로, 점들의 convex hull을 이용하는 방법이 있다.

어떠한 두 점을 이었을 때 볼록 껍질의 변과 해당 선이 교차하는 일은 일어나지 않는다.

따라서 볼록 껍질을 구한 뒤, 볼록 껍질 중 검은 점과 하얀 점이 연속으로 나타난다면, 해당 두 점을 이어주어도 그 외 점들을 이었을 때 생기는 선들과 교차하지 않는다.

따라서 볼록 껍질 상에서 이을 수 있는 점을 찾고, 이어진 점을 제외하고 다시 볼록 껍질을 생성하는 과정을 반복하면 된다.

 

이 때 한 가지 예외적인 상황이 발생할 수 있다. 볼록 껍질 내에 한가지 색의 점들만 존재하는 경우이다.

이 때 매우 기묘한 방법을 사용하여 타개해나가는 것이 가능하다.

볼록 껍질 상의 한 점을 기준 하여, 반시계 방향으로 선을 돌려나간다고 생각해보자.

이 때, 선의 아래쪽(선과 겹치는 것도 포함한다)에 놓이는 점들의 개수를 각각 세 보자.

볼록 껍질 상에 검정색 점만 존재하다고 가정해보자.

맨 처음에는 검정색 점 2개가 선의 아래에 놓이게 된다. (①번 선)

그리고 중간에는 어떤 순서로 나올지 모르니 넘어가고, 맨 마지막까지 가면 선 아래에 검정색 점 n개와 하얀색 점 n개가 놓이게 됨은 자명하다. (④번 선)

맨 마지막에 만나게 되는 점은 검정색 점일 것이므로, 그 직전에는 검정색 점 n - 1개, 하얀색 점 n개가 놓이게 될 것이다. (③번 선)

 

이 때, ①번 선과 ③번 선을 보자. 처음에는 검정색 점이 더 많았는데, 흰색 점이 더 많게 되었다.

값들은 점을 만날 때마다 1씩 변하므로, 중간 어딘가에서는 반드시 두 값이 같아지는 지점이 존재한다!

그리고 그 점은 반드시 흰색 점일 것이다.

반드시 흰색 점인 이유는, 흰색이 더 작은 값이었는데 값이 같아지는 상황이므로 흰색 점을 만나, 흰색의 count가 1 늘어나면서 값이 같아지는 상황만이 가능하기 때문이다.

 

이제 검정 점과 흰색 점을 선분으로 이어주면, 하나의 쌍을 추가하면서 동시에 선의 위쪽에도, 그리고 아래쪽에도 검정 점의 수와 흰색 점의 수가 같아지도록 만들 수 있다!

 

이제 선의 위쪽과 아래쪽에 각각에 대해 다시 문제를 반복해서 풀면 된다.

점의 convex hull을 찾는 시간 복잡도는 $O(n\log{n})$이고, 한 번 찾을 때마다 최소 하나의 쌍이 찾아지게 되므로 이 과정은 최대 $n$번 반복된다.

예외 케이스로 소개했던 볼록 껍질 상에 같은 색의 점만 놓이는 상황에도, 이미 convex hull을 구하며 ccw 기준으로 정렬이 되어 있을 것이고, 이를 훑는데 걸리는 시간은 $O(n)$이므로 시간 복잡도에는 영향을 미치지 않는다.

 따라서 총 시간 복잡도는 $O(n^2\log{n})$에 문제를 풀어낼 수 있다!

 

SCPC 4회 본선: 기판 문제 풀기

문제는 Codeground - Practice - 86번 문제에서 확인 가능하다.

무조건 가입을 해야 하는 것 같은데, SCPC도 칠 겸 다들 가입하자~!

 

문제는 같은데, 조건이 조금 다르다.

먼저 n = 50000이고, 점들이 랜덤하게 분포한다.

그리고 모든 점을 다 이어 줄 필요가 없다. 몇 개만 이으면 부분 점수를 주는데, 전체 점 중 70% 이상을 이으면 만점이다.

 

n이 크기 때문에 위 방법을 그대로 적용할 수는 없다.

고로 이 문제에서는 위 방법과 더불어 한 가지 사실을 더 이용할 것이다.

점을 (x좌표, y좌표) 순으로 정렬한 뒤 이를 원소들이 연속한 몇 개의 덩어리로 나누면 각 덩어리들의 convex hull은 disjoint하다는 사실이다.

말로 하면 어려운데, 그림을 보면 바로 알 수 있다. 12개의 점을 정렬한 뒤, 4개의 연속한 원소씩 3덩어리로 나눈 예시이다. 조금만 생각해보면 convex hull이 절대로 겹칠 수 없음을 알 수 있다.

 

따라서 문제를 풀기 위해, 우리는 주어진 점을 정렬한 뒤 적당한 크기의 덩어리들로 쪼갤 것이다.

덩어리의 크기는 최대 200(즉, n = 100)이 되도록 할 것인데(100은 엿장수 맘대로 정함), $O(n^2 \log{n})$에서 $n$이 너무 커지지 않게 하기 위함이다.

정렬한 순으로 쭉 훑다가, 검정 점과 하얀 점의 갯수가 중간에 같아진다면 바로 덩어리를 쪼갠 뒤, 위에서 소개한 방법을 통해 해당 덩어리 내의 점들을 모두 매칭시키는 것이 가능하다.

문제는 200개의 점을 훑었는데도 검정 점과 하얀 점의 갯수가 같아지는 경우가 발생하지 않는 경우이다. 이 때는 어쩔 수 없이 매칭에서 손실이 발생하게 된다.

하지만 이 때도, 위 방법을 조금만 응용하면 검정 점이 b개, 하얀 점이 w개 있다고 쳤을 때 min(b, w)개의 매칭을 무조건 찾아낼 수 있다.

간략히만 설명해보면, 일반성을 잃지 않고 b > w라고 해 보자.

convex hull을 구한 뒤 convex hull 상에 다른 색이 연속으로 나온다면 매칭해주는 것은 동일하게 진행하면 되고,

같은 색만 볼록 껍질 상에 놓일 경우,

검정색만 놓인다면 임의의 연속된 두 점을 그냥 제외시켜버리면 되고,

하얀색만 놓인다면 반시계 방향으로 선을 돌리는 방법을 통해 마찬가지로 하나의 쌍과, 쌍을 이은 선의 아래쪽에 같은 수의 검정/하얀 점이 놓이도록 만들어낼 수 있다. 이제 위쪽과 아래쪽을 다시 재귀적으로 풀면 된다.

 

결국 덩어리를 쪼갤 때 검정 점과 하얀 점이 얼마나 균등하게 섞여있느냐가 핵심인데, 만점을 맞지 않기 위해서는 200개의 점을 골랐을 때 이 중 30%에 해당하는, 60개의 점이 매칭이 되지 않아야 한다. 다시 말해, 한 가지 색이 130개 이상 있어야 한다.

이는 n=200, p=1/2인 이항 분포이며, 정규분포로 근사하면 N(100, 50)이다. 여기서 평균인 100으로부터 30개 이상 차이가 나게 되는 경우는 정규분포상의 $4.24\sigma$ 정도의 값으로, 확률은 $10^{-4}$보다도 작다.