[Python] 2013번 선그리기

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

2013번: 선그리기

---

22/08/25

 

 

4일 전쯤에 CCW 알고리즘을 배우고 나서 이를 응용한 선분 교차 판정 알고리즘을 배운 적이 있었다.

 

이를 활용하여 문제도 몇 개 풀어보았는데, 선분 교차 1, 선분 교차 2 등등... 그러한 문제들을 풀어봤다.

 

이것도 그러한 문제들 중에 한 문제이다.

 

때문에 이 문제의 풀이를 읽는다면 CCW알고리즘과 선분 교차 판정 알고리즘, 유니온-파인드 알고리즘에 관한 내용은 당연히 알고 있다는 가정 하에서 글이 서술이 되므로, 그 부분들을 먼저 공부를 하고 오면 더욱 이해가 잘 될 것이다.

 

---

 

초반 접근 방법:

 

 

일단 글이 개떡같이 쓰여있어서, 나는 선을 이어서 그릴 수 있다는 말을 꺾은 선도 포함해서 일컫는 말인 줄 알았다.

 

근데 당연히 그렇게 몇번이나 구현했는데 틀렸습니다를 받았다...

 

잘못된 구현방법은 다음과 같았다.

 

1. 일단 범위가 10000까지 입력을 받기 때문에, 두 개의 선분을 선택해서 만나는지 안 만나는지 판단하려면 nC2번을 판단해야 된다.

 

다시 말해, 시간 복잡도는 O(n^2) 정도 된다고 생각했고, 그러면 입력을 좀 빠르게 해야 돌아갈 수 있다고 생각하여 sys.stdin.readline으로 빠른 입력을 받았다.

 

 

2. 선을 만나는 거를 판단하는 부분은 CCW 알고리즘을 활용하여 구현하였다.

 

CCW 알고리즘을 통해 네 점이 한 직선 위에 있는 경우와 세 점이 한 직선위에 있는 경우를 나누고, 이 중 네 점이 한 직선 위에 있을 때 서로 선분이 겹치는 경우를 return 1, 아니면 return 0을 해주었다.

 

또한, 세 점이 한 직선 위에 있는 경우 중 한 점이 다른 한 점과 겹쳐질 때의 경우는 꺾은 선의 경우이므로 그때는 return 1, 아니면 return 0을 해주었다.

 

나머지 경우는 다 아니므로 return 0을 해주었다.

 

 

3. 선을 입력받고, reps배열을 만든 후, 두 인덱스를 뽑아 두 인덱스에 해당하는 선분이 서로 이을 수 있는 선이라면 두 인덱스에 해당하는 reps를 유니온 해주었다.

 

 

4. 이후 reps배열을 set으로 바꾸어 중복제거를 해주었고, 그 set의 길이를 print 하는 것으로 해주었다.

 

 

이후 나는 꺾은선이 아니라 선분이 서로 만나고, 선분끼리 서로 한 직선 위에 있는 경우만 선을 이어서 그릴 수 있다는 것으로 방향을 바꾸어서 풀어보았다.

 

---

 

두 번째 접근 방법:

 

그렇게 풀었는데도 틀렸습니다를 받았다....

 

주변 사람들에게 도움을 요청했고, 원인은 실수 오차 때문에 있다는 것을 알아냈다.

 

그렇게 고치고 냈다.

 

---

 

세 번째 접근 방법:

 

 

이번엔 유니온-파인드 부분이 문제였다.

 

마지막에 파인드를 전부다 한 번씩 돌려주는 것으로 고치고, 제출했더니 또 틀렸다....

 

알고 보니 재귀 깊이가 문제였고, 문제에서 주어지는 N의 제한이 10000까지 이길래 넉넉하게 50000으로 재귀 제한을 늘렸고, 맞았습니다를 받았다.

 

---

 

최종적인 접근 방법:

 

최종 접근 방법은 다음과 같다.

 

1. 일단 범위가 10000까지 입력을 받기 때문에, 두 개의 선분을 선택해서 만나는지 안 만나는지 판단하려면 nC2번을 판단해야 된다.

 

다시 말해, 시간 복잡도는 O(n^2) 정도 된다고 생각했고, 그러면 입력을 좀 빠르게 해야 돌아갈 수 있다고 생각하여 sys.stdin.readline으로 빠른 입력을 받았다.

 

이때, 실수 오차가 날 수 있으니 100을 곱해서 입력을 받는다.

 

또한, 유니온-파인드를 사용하고 맨 마지막에 find함수를 모든 인덱스에 대해 한 번씩 돌리는데, 그때 재귀 깊이 초과로 오류가 날 수 있으므로, sys.setrecursionlimit(50000)으로 설정했다. (N = 10000까지여서 넉넉하게 잡음)

 

 

2. 선을 만나는 거를 판단하는 부분은 CCW 알고리즘을 활용하여 구현하였다.

 

CCW 알고리즘을 통해 네 점이 한 직선 위에 있을 때 서로 선분이 겹치는 경우를 return 1, 아니면 return 0을 해주었다.

 

나머지 경우는 다 아니므로 return 0을 해주었다.

 

 

3. 선을 입력받고, reps배열을 만든 후, 두 인덱스를 뽑아 두 인덱스에 해당하는 선분이 서로 이을 수 있는 선이라면 두 인덱스에 해당하는 reps를 유니온 해주었다.

 

 

4. 이후 reps배열을 한 번씩 find함수를 돌려 인덱스를 한 곳만 가리키도록 압축시켜주었다.

 

set으로 바꾸어 중복제거를 해주었고, 그 set의 길이를 print 하는 것으로 해주었다.

 

---

 

위의 최종 접근 방법을 통해 내가 작성한 파이썬 코드는 다음과 같다. 더보기를 누르면 확인할 수 있다. 참고로, pypy로 제출하였다.(python은 시간 초과가 떴음)

# 2013번 선그리기
# 선분교차판정, 기하학
'''
CCW를 이용한 선분 교차 판정 중 네 점이 모두 한 직선위에 있고 서로 겹쳐지는 경우
+
유니온 파인드
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

def dir_vec(p1, p2):
    return (p2[0] - p1[0], p2[1] - p1[1])
def cross_product(vec_a, vec_b):
    return vec_a[0]*vec_b[1] - vec_a[1]*vec_b[0]
def CCW(p1, p2, p3):
    vec_a = dir_vec(p1, p2)
    vec_b = dir_vec(p2, p3)
    k = cross_product(vec_a, vec_b)
    if k > 0:
        return 1
    elif k < 0:
        return -1
    else:
        return 0
def point_compare(p1, p2):
    if p1[0] > p2[0]:
        return p1
    elif p1[0] < p2[0]:
        return p2
    else:
        if p1[1] >= p2[1]:
            return p1
        else:
            return p2
def point_swap(p1, p2):
    if point_compare(p1, p2) == p1:
        return p2, p1
    else:
        return p1, p2
def line_swap(p1, p2, p3, p4):
    if point_compare(p1, p3) == p1:
        return p3, p4, p1, p2
    else:
        return p1, p2, p3, p4
def can_draw_once(line1, line2):
    p1, p2 = point_swap(line1[0], line1[1])
    p3, p4 = point_swap(line2[0], line2[1])
    if CCW(p1, p2, p3) == 0 and CCW(p1, p2, p4) == 0: # 네 점이 한 직선 위에 있고
        p1, p2, p3, p4 = line_swap(p1, p2, p3, p4)
        if point_compare(p2, p3) == p2 or p2 == p3:
            return 1
        else:
            return 0
    else:
        return 0
def find(node):
    if reps[node] != node:
        reps[node] = find(reps[node])
    return reps[node]
def union(node1, node2):
    rep1 = find(node1)
    rep2 = find(node2)
    reps[rep2] = rep1

N = int(input())
reps = [i for i in range(N)]
lines = []
for _ in range(N):
    x1, y1, x2, y2 = map(lambda x: int(round(float(x)*100)), input().rstrip().split())
    line = ((x1, y1), (x2, y2))
    lines.append(line)
for i in range(N-1):
    for j in range(i+1, N):
        if can_draw_once(lines[i], lines[j]):
            union(i, j)
for i in range(N):
    find(i)
print(len(set(reps)))