[Python] 백준 - 2162 선분 그룹

문제

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

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

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

 

입력

 

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

출력

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

 

필요한 도구

 

 

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

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

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

 

문제해결방법

 

 

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. 판별식을 구현했으면, 유니온 파인드 알고리즘을 이용해 그룹화를 한다. 

 

- 코드

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))