[백준] 2162번: 선분 그룹 - 파이썬

문제이해

선분들이 주어질 때, 그 선분들이 교차하거나 닿는 부분이 있다면 같은 그룹으로 묶고, 아니라면 다른 그룹으로 취급하여, 그룹의 개수와 그룹들 중 선분이 가장 많은 그룹의 선분 개수를 출력하는 문제이다.

계획

이 문제는 두가지 부분으로 나눠진다. 

1. 먼저 선분 두 개가 주어졌을 때 교차하는지 확인하는 함수가 필요하다.

2. 만약 교차할때, 같은 그룹으로 묶어주는 함수가 필요하다.

1번 같은 경우는 ccw를 이용하여요 선분이 교차하거나 맞닿는지 확인하면 되고, 2번 같은 경우는 union-find를 이용해서 같은 그룹으로 묶어주면 된다.

마지막으로, 그룹의 크기를 출력해야하므로 union 할 때마다 각 그룹의 root에 해당하는 원소에 그룹의 위치를 계속해서 저장해 주면 나중에 쉽게 출력할 수 있다.

1번의 경우는 다음과 같이 수행하면된다.

i. x1, y1, x2, y2 나 x3, y3, x4, y4가 주어질 때 한 줄에 주어지는 2개의 좌표는 한 개의 선분이므로, 같은 그룹으로 묶어줘야 한다.

ii. ccw를 통해 두 개의 선분이 교차하거나 맞닿는지 확인한다.

iii. 만약 맞닿거나 교차한다면, 같은 그룹으로 묶어준 후, 그룹의 개수를 늘려준다. 만약 그렇지 않다면, 패스한다.

iv. 모두 확인했다면, 그룹이 저장된 배열을 다시 순회하며 그룹의 개수와 제일 큰 그룹의 선분 개수를 구해주고 출력하면 된다.

계획수행

import sys

n = int(sys.stdin.readline())
p = [[] for _ in range(2*n)]    #좌표값을 저장하기 위한 배열
r = [i for i in range(2*n)]     #union-find를 위한 배열
dp = [1 for i in range(2*n)]    #그룹의 크기를 저장하는 배열
v = [False for i in range(2*n)] #그룹의 개수를 셀때 필요한 배열

#union-find t가 있는 트리의 루트값 찾기
def find(t):    
    if t == r[t]: return t
    r[t] = find(r[t])
    return r[t]

#만약 이미 같은 그룹이라면 True 반환
#아니라면 같은 그룹으로 묶어주고 False 반환
def union(a, b):
    a, b = find(a), find(b)
    if a == b: return True
    if a < b:
        a, b = b, a
    r[a] = b
    dp[b] += dp[a]
    return False

#ccw
def ccw(a1, b1, a2, b2, a3, b3):
    return a1*b2+a2*b3+a3*b1-b1*a2-b2*a3-b3*a1

#선분 a와 선분 b가 교차하거나 맞닿는지 확인
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 True
            return False
        else:    #두선분이 교차한다면
            return True
    return False

for i in range(n):
    x1, y1, x2, y2 = list(map(int, sys.stdin.readline().split()))
    p[2*i] = (x1, y1)
    p[2*i+1] = (x2, y2)
    union(2*i, 2*i+1)    #같은 이므로 묶어주기

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

group = []
for i in range(2*n):
    if v[i]: continue    #이미 방문했으면 이미 센 그룹
    a = find(i)
    group.append(a)      #이미 세지 않았다면 해당 원소가 해당하는 트리의 루트에 해당하는 값 gruop에 추가
    for ii in range(2*n):
        if a == find(ii): v[ii] = True    

ans = 0
for i in group: ans = max(ans, dp[i])    #루트들 순회하며 제일 큰 그룹 찾기

print(len(group))
print(ans//2)    #하나의 선분에는 두개의 좌표가 있으므로 나누기 2해야함

 

 

느낀 점

이 문제도 하나하나 따져가며 구분하며 풀면 쉬웠던 문제였다. 처음에는 좌표값을 딕셔너리에 저장하고 거기에 union-find를 적용하려 했으나, 시간복잡도도 올라가고 다른 배열을 다루기도 어려웠고, 같은 좌표값이 나오면 덮어 써져서 고민하다가 위와 같이 index를 다루는 또 다른 배열을 추가하여 쉽게 풀었다. union-find로 다루기 어려울 거 같으면 index를 사용하는 방법도 고민해 봐야겠다.