Baekjoon 2162. 선분 그룹 / Python

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

2162번: 선분 그룹

### Python

- 함수 설명

1. union_find : 노드의 루트 노드를 찾는 함수

2. union_set : 두 노드가 속한 그룹을 합치는 함수

3. CCW : 세 점의 방향을 계산하는 함수

4. check : 두 선분의 교차여부를 판단하는 함수

- 알고리즘 설명

1. 입력된 선분들의 교차여부를 판단하여 같은 그룹으로 묶는다.

2. 이 과정에서 유니온-파인드 알고리즘을 이용하여 이미 처리된 노드를 건너 뛰고, 루트 부모를 찾는다.

3. 결론 : 플래티넘5치고 어렵지 않았다. (물론, CCW와 유니온-파인드를 알고 있다면....)

import sys; input = sys.stdin.readline

# 선분의 개수
n = int(input())

# 선분의 좌표를 저장할 리스트, 총 2*n개의 좌표가 저장됨
arr = [[] for _ in range(2 * n)]

# 유니온-파인드 알고리즘을 위한 부모 노드 리스트 초기화
parent = [i for i in range(2 * n)]

# 각 노드가 속한 그룹의 크기를 저장할 리스트
dp = [1 for i in range(2 * n)]

# 각 노드가 이미 처리되었는지 여부를 저장할 리스트
cnt = [False for i in range(2 * n)]

# 유니온-파인드 알고리즘의 find 연산: 루트 노드를 찾는 함수
def union_find(x):
    if x == parent[x]: return x
    parent[x] = union_find(parent[x])
    return parent[x]

# 유니온-파인드 알고리즘의 union 연산: 두 그룹을 합치는 함수
def union_set(x, y):
    x, y = union_find(x), union_find(y)
    if x == y: return 1
    if x < y:
        x, y = y, x
    parent[x] = y
    dp[y] += dp[x]
    return False

# CCW(Counter ClockWise)를 이용한 세 점의 방향성을 구하는 함수
def ccw(a1, b1, a2, b2, a3, b3):
    return a1 * b2 + a2 * b3 + a3 * b1 - b1 * a2 - b2 * a3 - b3 * a1

# 두 선분이 교차하는지 확인하는 함수
def check(a, b):
    l1 = ccw(a[0], a[1], a[2], a[3], b[0], b[1]) * ccw(a[0], a[1], a[2], a[3], b[2], b[3])
    l2 = ccw(b[0], b[1], b[2], b[3], a[0], a[1]) * ccw(b[0], b[1], b[2], b[3], a[2], a[3])
    if l1 <= 0 and l2 <= 0:
        if l1 == 0 and l2 == 0:
            d1 = max(a[0], a[2]) >= min(b[0], b[2]) and max(b[0], b[2]) >= min(a[0], a[2])
            d2 = max(a[1], a[3]) >= min(b[1], b[3]) and max(b[1], b[3]) >= min(a[1], a[3])
            if d1 and d2:
                return 1
            return 0
        else:
            return 1
    return 0

# n개의 선분에 대해 입력을 받아 처리하는 루프
for i in range(n):
    x1, y1, x2, y2 = list(map(int, input().split()))
    arr[2 * i] = (x1, y1)
    arr[2 * i + 1] = (x2, y2)
    union_set(2 * i, 2 * i + 1)

    for j in range(i):
        a = (x1, y1, x2, y2)
        b = (arr[2 * j][0], arr[2 * j][1], arr[2 * j + 1][0], arr[2 * j + 1][1])
        if check(a, b):
            union_set(2 * i, 2 * j)

# 그룹을 찾고 각 그룹의 크기를 계산하는 부분
group = []
for i in range(2 * n):
    if cnt[i]: continue
    a = union_find(i)
    group.append(a)
    for j in range(2 * n):
        if a == union_find(j): cnt[j] = 1

# 최대 그룹 크기를 찾는 부분
res = 0
for i in group: res = max(res, dp[i])

# 그룹의 개수와 최대 그룹의 크기
print(len(group))
print(res // 2)