백준(BOJ) 2162 선분 그룹(Python)

문제 내용

 

Union-Find에 선분 교차 판정을 곁들인 문제.

각 선분이 모두 교차하는지 확인하고, 교차한다면 Union-Find를 진행하면 되는 문제.

일반적인 선분 교차 판정과는 달리 두 선분이 하나로 겹쳐지는 경우나 한 점에서 접하는 경우도 포함해야 하기 때문에 이 부분을 고려해서 선분 교차 판정을 수정해줬다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
L=[list(map(int,input().split())) for i in range(n)]
cycle=[i for i in range(n)]
    
def find(u):
    if u!=cycle[u]:
        cycle[u]=find(cycle[u])
    return cycle[u]

def union(u,v):
    u=find(u)
    v=find(v)
    cycle[v]=cycle[u]

def ccw(x1,y1,x2,y2,x3,y3,x4,y4):
    a=(x3-x2)*(y2-y1)
    b=(y3-y2)*(x2-x1)
    c=(x4-x2)*(y2-y1)
    d=(y4-y2)*(x2-x1)
    
    k1=0
    k2=0
    if a>b:
        k1=-1
    elif a<b:
        k1=1
    if c>d:
        k2=-1
    elif c<d:
        k2=1
    if k1==k2:
        if k1==0:
            i=min(x1,x2)
            j=max(x1,x2)
            if i<x3<j or i<x4<j:
                return 1
            i=min(y1,y2)
            j=max(y1,y2)
            if i<y3<j or i<y4<j:
                return 1
            i=min(x3,x4)
            j=max(x3,x4)
            if i<x1<j or i<x2<j:
                return 1
            i=min(y3,y4)
            j=max(y3,y4)
            if i<y1<j or i<y2<j:
                return 1
        return 0
    else:
        k3=0
        k4=0
        e=(x1-x3)*(y4-y3)
        f=(y1-y3)*(x4-x3)
        g=(x2-x3)*(y4-y3)
        h=(y2-y3)*(x4-x3)
        if e>f:
            k3=-1
        elif e<f:
            k3=1 
        if g>h:
            k4=-1
        elif g<h:
            k4=1
        if k3==k4:
            return 0
        else:
            return 1
p=0
while p<n-1:
    for i in range(p+1,n):
        if ccw(L[p][0],L[p][1],L[p][2],L[p][3],L[i][0],L[i][1],L[i][2],L[i][3]):
            if find(p)!=find(i):
                union(p,i)
    p+=1
D={}
for i in range(n):
    k=find(i)
    if k not in D.keys():
        D[k]=1
    else:
        D[k]+=1
print(len(D))
print(max(D.values()))

 

이전에 풀었던 문제들에서 코드를 가져와 수정해서 풀었다.

사실 아직 실력이 부족해서 직접 구현해봐야 하지만,,, 그냥 가져오면 편한데 왜 굳이 구현을 할까 싶어서.

예전에 풀었던 문제가 완전 기본형이라 가져와도 큰 무리가 없었다.