[백준 2162번] 선분 그룹 (Python3)

import sys
input = sys.stdin.readline

def findparent(x):
  if parent[x] == x:
    return x
  parent[x] = findparent(parent[x])
  return parent[x]

def eq(x,y,i):
  return (x2[i]-x1[i])*(y-y1[i])-(y2[i]-y1[i])*(x-x1[i])

def check(i,j):
  if eq(x1[j],y1[j],i)*eq(x2[j],y2[j],i)<=0 and eq(x1[i],y1[i],j)*eq(x2[i],y2[i],j)<=0:
    if x2[i]-x1[i] == x2[j]-x2[j] == 0:
      if max(y1[i],y2[i])>=min(y1[j],y2[j]) and max(y1[j],y2[j])>=min(y1[i],y2[i]):
        return 1
    elif (y2[j]-y1[j])*(x2[i]-x1[i]) == (y2[i]-y1[i])*(x2[j]-x1[j]):
      if y1[i]-(y2[i]-y1[i])/(x2[i]-x1[i])*x1[i] == y1[j]-(y2[j]-y1[j])/(x2[j]-x1[j])*x1[j]:
        if max(x1[i],x2[i])>=min(x1[j],x2[j]) and max(x1[j],x2[j])>=min(x1[i],x2[i]):
          return 1
    else:
      return 1
  return 0


N = int(input())
x1,y1,x2,y2 = [0]*N,[0]*N,[0]*N,[0]*N
for i in range(N):
  x1[i],y1[i],x2[i],y2[i] = map(int,input().split())

parent = {i:i for i in range(N)}

for i in range(N):
  for j in range(N):
    if findparent(i) != findparent(j):
      if check(i,j):
        if parent[i] < parent[j]:
          parent[parent[j]] = parent[i]
        else:
          parent[parent[i]] = parent[j]

cnt = 0
parentcnt = [0]*N
for i in range(N):
  x = findparent(i)
  if parentcnt[x] == 0:
    cnt += 1
  parentcnt[x] += 1

print(cnt)
print(max(parentcnt))

 

선분교차2를 약간 응용한 문제이다.

알고리즘 자체는 선분교차2와 똑같다. 거기에 union-find만 살짝 결합시켜주면 된다.

 

선분그룹2의 선분교차 판별을 함수로 지정하고 이중 for문을 돌면서 두 선분이 교차한다면 같은 그룹에 union 시켜주면 된다.

 

두개의 알고리즘을 잘 버무린 재밌는 문제였다.

 

 

오늘의 교훈) union-find 알고리즘을 잘 활용하자