[Python] 백준 3679 - 단순 다각형

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

 

문제

평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.

예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.

항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.

입력

첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌표 x와 y이며, 좌표는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

각 테스트 케이스마다 0부터 n-1까지 순열중 하나를 출력해야 한다. 출력하는 순열은 입력으로 주어지는 점의 번호를 나타내며, 출력하는 순서대로 점을 이었을 때, 올바른 다각형을 만들어야 한다.

 

---

풀이

컨벡스 헐 응용 문제이다.

컨벡스 헐을 사용하는 다른 풀이들도 많을 것으로 보이나, 이 문제가 컨벡스 헐 문제에 포함된 진정한 이유는

그래햄 스캔 알고리즘과 앤드류 알고리즘의 원리를 잘 이해하고 응용할 수 있는가?

인 것 같다.

 

 

다른 많은 풀이들은 CCW나, 정렬 함수를 직접 만들어 사용 한 것으로 보이는데

나는 그런 것들이 쉽게쉽게 떠오르지 않아서 직접 다른 쉬운 방법을 생각해보았다.

 

 

먼저, 직관적으로 이 문제를 풀기 위해서 그래햄 스캔 알고리즘이 떠올랐다.

어떠한 특정 점을 잡고 반시계 방향으로 정렬하는 것이다.

보통의 그래햄 스캔 알고리즘이라면 스택에 점들을 관리하면서 CCW를 검사해주며 방향이 맞지 않는 점들을 계속 빼주었을 것인데, 

여기서는 그럴 필요가 없다.

그냥 순서대로 모든 점들을 이어주면 문제가 되지 않을 것이다.

 

내가 처음 생각한 알고리즘

(이 풀이는 틀린 풀이이다)

처음에는 여러가지 테스트케이스에 대해서 다음과 같은 알고리즘을 생각했었다.

1. y좌표, x좌표가 가장 작은 점을 피벗으로 잡는다.

2. 피벗을 기준으로 반시계 기준으로 정렬하고, 각도가 같다면 x좌표가 작은 순으로, 그것마저 같다면 y좌표순으로 정렬한다.

 

직접 그림을 그려서 풀이해보면 웬만한 테스트케이스에 대해서는 맞는 풀이이다.

 

그런데, 무슨 일인지 계속 25%에서 틀리는 것이다.

분명 알고리즘에서 뭔가 틀린 것이 있을 것이다.

 

 

게시판의 도움을 받아, 다음과 같은 상황에서 반례가 생김을 알 수 있었다.

 

 

지금 보니까 엄청나게 멍청하다ㅠㅠ 점들이 각도가 같은 경우를 조금 더 일반화해서 생각해줬어야했는데 x좌표가 같은 특수한 경우만 생각하다니ㅠㅠ

 

내가 나중에 생각한 알고리즘

(이 풀이는 맞는 풀이이다)

 

치명적인 반례 1개로 알고리즘 자체가 부정당했기 때문에 알고리즘을 다음 날 다시 짜보았다.

지난번과 아이디어 자체는 비슷하게 가는데, 각도가 같은 경우 정렬을 조금 다르게 한다.

 

1. y좌표, x좌표가 가장 작은 점을 피벗으로 잡는다.

2. 피벗을 기준으로 반시계 기준으로 정렬하고, 각도가 같다면 피벗과의 거리가 먼 순으로 정렬한다.

3. 가장 각도가 작은 점들(1개가 될 수도 있다)에 대해서는 특수하게 피벗과의 거리가 작은 순으로 정렬한다.

 

원래 있었던 x, y좌표 기준 정렬을 거리순 정렬 한 번으로 특수한 경우에 대해서도 훨씬 일반적으로 작동하게 만들었다.

여기서 핵심은 원래 없었던 3번이다.

3번이 왜 추가되었는지 그림을 통해 알아보자.

 

아까의 반례이다.

pivot을 시작점과 끝점으로 잡으면,

점들을 반시계 방향으로 정렬했기 때문에

처음에는 나가는 방향의 순서, 맨 마지막에는 들어오는 방향의 순서로 오면 될 것이다.

 

각도가 같은 점들이 많은 다른 그림을 보자.

 

처음에만 나가고 나중에는 전부 들어오는 방향으로 해도 문제가 없을 것이다.

도형을 직접 그려보면 다음과 같다.

그럼 우리는 일반적으로

"아, 맨 처음 각도에 대해서만 거리가 작은 순으로 정렬하면 되겠구나"

하고 생각할 수 있다.

 

맨 처음 각도에 속하는 점이 1개밖에 없어도 이 아이디어는 성립한다.

 

 

이제 이 아이디어를 코드로 짜보자.

 

tmp = list(map(int, input().split()))
dots = []
cnt = 0
for i in range(1, 2*tmp[0]+1, 2):
    dots.append((tmp[i],tmp[i+1],cnt))
    cnt += 1
dots.sort(key=lambda x:(x[1], x[0]))
pivotx, pivoty, num = dots.pop(0)

 

점들을 입력받고, 피벗을 정하는 코드이다.

 

여기서 정렬을 쉽게 하기 위해 cal이라는 함수를 정의한다.

def cal(X):
    x = X[0] - pivotx
    y = X[1] - pivoty
    angle = math.atan2(y, x)
    angle *= 1e9
    angle = int(angle)

    dist = x**2 + y**2

    return angle, -dist, X[2]

 

리턴 값은 튜플이다.

각도를 계산할때는 math 함수의 atan2를 사용했다(이거 생각보다 정확하다)

 

리턴 값은 차례대로

각도

-거리(그래야 큰 순으로 정렬되니까)

점 번호

이다.

 

dots = list(map(cal, dots))
dots.sort()

 

map를 이용해서 점들을 튜플로 바꿔주고 정렬하면 쉽게 여러가지 조건에 대해서 정렬을 할 수 있다.

 

tmpidx = 0
while dots[tmpidx+1][0] == dots[tmpidx][0]:
    tmpidx += 1

print(num, end = ' ')
for i in range(tmpidx, -1, -1):
    print(dots[i][2], end=' ')
for i in range(tmpidx+1, len(dots)):
    print(dots[i][2], end=' ')
if _ != c-1:
    print()

 

다음으로 이렇게 코드를 짜면 맨 처음 각도에 해당되는 점들에 대해서는 역순으로 정렬이 된다.

 

맨 마지막에 테스트케이스가 끝났을 때는 줄바꿈을 하지 않는 특수 처리가 들어갔는데, 스페셜 저지 문제인지 이렇게 안하면 틀린다고 게시판 사람들이 말해주고 있었다.

 

그럼 전체 코드는 다음과 같이 간단하게 짤 수 있다.

 

c = int(input())
import math

def cal(X):
    x = X[0] - pivotx
    y = X[1] - pivoty
    angle = math.atan2(y, x)
    angle *= 1e9
    angle = int(angle)

    dist = x**2 + y**2

    return angle, -dist, X[2]

for _ in range(c):
    tmp = list(map(int, input().split()))
    dots = []
    cnt = 0
    for i in range(1, 2*tmp[0]+1, 2):
        dots.append((tmp[i],tmp[i+1],cnt))
        cnt += 1
    dots.sort(key=lambda x:(x[1], x[0]))
    pivotx, pivoty, num = dots.pop(0)

    dots = list(map(cal, dots))
    dots.sort()
    #print(dots)

    tmpidx = 0
    while dots[tmpidx+1][0] == dots[tmpidx][0]:
        tmpidx += 1

    print(num, end = ' ')
    for i in range(tmpidx, -1, -1):
        print(dots[i][2], end=' ')
    for i in range(tmpidx+1, len(dots)):
        print(dots[i][2], end=' ')
    if _ != c-1:
        print()