[Python] 백준 - 2162 선분 그룹

백준 - 2162 선분 그룹

문제

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

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

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

 

입력

 

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

출력

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

 

 

필요한 도구

 

 

1. 신발끈 공식으로 삼각형의 방향을 판별하는 함수

2. 1을 이용해 선분의 교차를 판별하는 함수

3. 유니온 파인드(Union Find) 알고리즘 - 그룹화를 판단

 

문제해결방법

 

 

1. 선분의 교차를 판단하는 방법은 이전 문제에서 빌드업하면서 차차 알 수 있게 구성되어 있다.

[Python] 백준 - 20149 선분 교차 3

 

이 문제는 이전 문제와 다르게 선분의 교차만을 판별하면 되므로 좀 더 쉽다. 

 

2. 직선 (x1, y1), (x2, y2) 과 각 점인 (x3, y3)과 (x4, y4)의 방향을 판별해본다.(A) 각 결과를 곱했을 때, 1이 나오면 안된다는 걸 알 수 있다. 직선 (x3, y3), (x4, y4)으로도 판별해본다.(B) 

 

1) A <= 0 and B <= 0의 경우에만 교차가 있을 수 있다. 그런데 A == 0 and B == 0 의 경우에는 예외가 있다.

 

 

2) 그림의 1사분면의 경우같이 같은 직선인데, 교차점이 없는 경우도 A == 0 and B == 0에 속한다. 위 그림의 경우는 True로 판별하면 안된다. check함수를 통해 이런 경우는 추려질 수 있도록 한다.

 

3. 판별식을 구현했으면 유니온 파인드(Union Find) 알고리즘을 이용해 그룹화를 한다. 

 

- 코드

import sys
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
parent = [i for i in range(n)]

def FIND(x):
    if parent[x] != x:
        parent[x] = FIND(parent[x])
    return parent[x]

def UNION(x, y):
    x = FIND(x)
    y = FIND(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

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

def check(x1, y1, x2, y2, x3, y3, x4, y4):
    A = min(x1, x2) <= max(x3, x4) and min(x3, x4) <= max(x1, x2)
    B = min(y1, y2) <= max(y3, y4) and min(y3, y4) <= max(y1, y2)
    return A and B

def meet(line1, line2):
    x1, y1, x2, y2 = line1
    x3, y3, x4, y4 = line2
    A = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4)
    B = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2)
    if A == 0 and B == 0:
        if check(x1, y1, x2, y2, x3, y3, x4, y4):
            return True
    else:
        if A <= 0 and B <= 0:
            return True
    return False

for i in range(n-1):
    for j in range(i+1, n):
        if meet(d[i], d[j]):
            UNION(i, j)

cnt = 0
v = [0 for _ in range(n)]
for i in range(n):
    if i == parent[i]:
        cnt += 1
    v[FIND(i)] += 1
print(cnt)
print(max(v))