[코딩 테스트 연습(파이썬/Python)] 백준 2162번 _ 선분 그룹

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

2162번: 선분 그룹

[문제]

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

 

[입력]

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

[출력]

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

 

[아이디어]

1) CCW를 이용해 선분의 교차 여부를 확인한다.

2) 선분이 교차하는 경우 유니온-파인드 알고리즘을 이용해 root를 동일하게 바꾸면서, root에 해당하는 노드가 가진 선분의 갯수를 업데이트 한다.

3) 모든 노드는 선분의 개수를 1개 가지고 시작하도록 초기화한다.

 

import sys
input=sys.stdin.readline

n=int(input())
p = [tuple(map(int,input().split())) for _ in range(n)]
d = [[i,1] for i in range(n)]

def root(x):
    if d[x][0]==x:
        return x
    d[x][0] = root(d[x][0])
    return d[x][0]
def union(x,y):
    rx = root(x)
    ry = root(y)
    if rx==ry:
        return
    d[ry][0] = rx
    d[rx][1] = d[rx][1] + d[ry][1]

def ccw(a,b,c,d,e,f):
    return (c-a)*(f-b)-(e-a)*(d-b)

def f(A,B):
    a,b,c,d = A; x,y,xx,yy = B
    tmp1 = ccw(a,b,c,d,x,y)*ccw(a,b,c,d,xx,yy)
    tmp2 = ccw(x,y,xx,yy,a,b)*ccw(x,y,xx,yy,c,d)
    if tmp1==tmp2==0:
        return 1 if min(a,c)<=max(x,xx) and min(x,xx)<=max(a,c) and min(b,d)<=max(y,yy) and min(y,yy)<=max(b,d) else 0
    else:
        return tmp1<=0 and tmp2<=0

for i in range(n):
    for j in range(i+1,n):
        if f(p[i],p[j]) and root(i)!=root(j):
            union(i,j)
roots = set(root(i) for i in range(n))
ans = 0
for r in roots:
    ans = max(ans,d[r][1])
print(len(roots))
print(ans)