[백준 2162번] 파이썬 - 선분 그룹

백준 2162-선분 그룹

시간 제한 2초, 메모리 제한 128MB

# 조건

• N개의 선분들이 2차원 평면상에 주어졌다.
• 선분은 양 끝점의 x, y좌표로 한다.
• 두 선분이 서로 만나는 경우, 두 선분은 같은 그룹에 속한다고 정의
• 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의
• 두 선분이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어있을까?
• 또, 가장 큰 그룹에 속한 선분의 개수는 몇 개일까?

입력

• 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다.
• 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다.
• 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

출력

• 첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

# 접근 방법

• 우선, 선분이 교차하는지를 판단하여야 한다.
  • ccw알고리즘을 이용하여 해당 여부 판별
  • https://cheon2308.tistory.com/entry/Algorithm-CCW-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• 즉, CCW(A, B, C) * CCW(A, B, D) <= 0 && CCW(C, D, A) * CCW(C, D, B) <= 0 이면, 교차한다고는 일단 할 수 있다.
• 네 직선이 한 직선상에 존재하는 경우 -> ccw 의 곱이 0이다.
  • 직선이 교차일 가능성이 있지만, 선분이 만나지 못하는 경우 -> 0보다 크거나 같다.
  • 즉, 모든 조건을 확인하기 위하여 4번의 ccw를 수행해주면 된다.
• 또한, 집합을 구해야 하므로 find, union 함수를 이용하여 관계를 업데이트 시켜준다.
  • 1번과 2번이 만나면 disjoint[2]를 0으로 업데이트, 이후 2번과 3번이 만난다면
  • union을 통하여 disjoint[3]을 0으로 업데이트 시켜준다.
• 마지막에 한번더 find를 사용하여 경로 압축을 해준다.
  • union은 단순하게 집합의 대표를 합치는 것이기 때문에
  • find를 통하여 그 시점의 집합을 대표하는 요소로 갱신해줘야하기 때문.

import sys  
sys.stdin = open('input.txt')  

def find(a):  
    if parent[a] == a:  
        return a  
    else:  
        parent[a] = find(parent[a])  
        return parent[a]  
def union(x, y):  
    parentX = find(x)  
    parentY = find(y)  
    if parentX > parentY:  
        parent[parentX] = parentY  
    elif parentY > parentX:  
        parent[parentY] = parentX  

def ccw(x1, y1, x2, y2, x3, y3):  
    tmp = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)  
    if tmp > 0:  
        return 1  
    elif tmp < 0:  
        return -1  
    else:  
        return 0  

n = int(input())  
segment = [[*map(int, input().split())] for _ in range(n)]  
parent = [i for i in range(n)]  
for i in range(n):  
    for j in range(i+1, n):  
        flag = False  
        answer = 0  
        x1, y1, x2, y2 = segment[i]  
        x3, y3, x4, y4 = segment[j]  
        if ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) == 0 and ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4,x2, y2) == 0:  
            flag = True  
            if min(x1, x2) <= max(x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max(y3, y4) and min(y3, y4) <= max(y1, y2):  
                answer = 1  
        if ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 and ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3,x4, y4, x2, y2) <= 0:  
            if not flag:  
                answer = 1  
        if answer == 1:  
            union(i,j)  

for i in range(n):  
    parent[i] = find(parent[i])  
k = set(parent)  
max_result = 0  
for u in parent:  
    if parent.count(u) > max_result:  
        max_result = parent.count(u)  
print(len(k))  
print(parent.count(max(set(parent),key=parent.count)))