[백준 / BOJ][Python] 2162 - 선분 그룹

[백준 / BOJ][Python] 2162 - 선분 그룹

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

2162번: 선분 그룹

문제 풀이

선분 교차 판정 + 유니온 파인드 이용하는 문제. 교차하는 선분들이 있다면 같은 그룹에 속하는 선분이라는 뜻이기에 Union 작업을 실시하면 된다. N ≤ 3,000 이므로 모든 조합을 시도해도 대략 450만 정도의 수가 나온다. 즉, Naive하게 풀이를 진행하면 된다. 추가로, 모든 Union 과정이 끝난 후 각 선분들의 번호에 대해 Find를 한번씩 진행해야 한다. 그렇지 않으면 마저 갱신되지 못한 번호들이 남아있을 수 있기 때문.

코드

import sys, itertools
input = sys.stdin.readline

def ccw(p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)

def line_intersection(p1, p2, p3, p4): #선분 교차 판정
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    x4, y4 = p4
    cross1 = ccw(p1, p2, p3) * ccw(p1, p2, p4)
    cross2 = ccw(p3, p4, p1) * ccw(p3, p4, p2)
    if cross1 == cross2 == 0:
        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):
            return 1
    elif cross1 <= 0 and cross2 <= 0:
        return 1
    return 0

def find(x):
    if graph[x] != x:
        graph[x] = find(graph[x])
    return graph[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        graph[y] = x
    else:
        graph[x] = y

n = int(input())
graph = [i for i in range(n + 1)] #Union Find 연산을 실행할 list
lines = [] #선분들을 저장할 list
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    lines.append([i + 1, [x1, y1], [x2, y2]]) #[번호, 시작점, 끝점]
for i in itertools.combinations(lines, 2): #가능한 모든 조합 (combination(n, 2))
    a, p1, p2 = i[0]
    b, p3, p4 = i[1]
    if line_intersection(p1, p2, p3, p4): #두 선분이 교차한다면
        union(a, b) #한 그룹으로 묶어준다.
for i in range(1, n + 1):
    graph[i] = find(i) #Union 후 모든 선분 번호들에 대해 Find 갱신
num_set = list(set(graph))
num_set.remove(0)
ans = 0
for i in num_set:
    ans = max(graph.count(i), ans)
print(len(num_set)) #총 그룹의 수
print(ans) #가장 많은 선분을 보유한 그룹의 선분 수