백준 2162번: 선분 그룹 (선분교차 판정)

문제링크:2162번: 선분 그룹 (acmicpc.net)

2162번: 선분 그룹

이 문제는 선분이 여러개 주어질 때, 어떤 선분이 다른 선분과 교차할 때 교차하는 선분들을 그룹짓는 문제이다. 선분 교차를 판별하는 백준 문제 17387번을 먼저 풀면 도움이 될 것이다. 처음 17387번을 풀때 나는 좌표 위의 점들을 통해 두 선분의 방정식을 구하고,연립하여 교점을 구하는 방식으로 문제를 풀어냈다. 하지만 약 3000개의 해당하는 선분들의 각 교차를 판단하려면 최악의 경우 교차 판단 연산을 3000! 만큼 수행해야 하는데, 방정식을 연립하여 푸는 방법은 무조건 시간 초과가 날 것 같아 인터넷에 검색하여 벡터의 외적을 이용한 선분 교차 판단 알고리즘에 대해 알 수 있었다.

import sys

N=int(sys.stdin.readline().rstrip())

linelst=[]
parent=[i for i in range(N)]
parentcnt=[0 for _ in range(N)]
for _ in range(N):
    a,b,c,d=map(int,sys.stdin.readline().rstrip().split())
    pointlst=[[a,b],[c,d]]
    linelst.append(pointlst)
    
def ccw(a,b,c): #선분 pa-pb, pa-pc의 외적의 k성분 반환
    v1=[b[0]-a[0],b[1]-a[1]]
    v2=[c[0]-a[0],c[1]-a[1]]
    return (v1[0]*v2[1])-(v1[1]*v2[0])
    
def intersect(a,b): #linelst[a], linelst[b]선분 교차하는지 판단
    ap1=linelst[a][0]
    ap2=linelst[a][1]
    bp1=linelst[b][0]
    bp2=linelst[b][1]
    accw=ccw(ap1,ap2,bp1)*ccw(ap1,ap2,bp2)
    bccw=ccw(bp1,bp2,ap1)*ccw(bp1,bp2,ap2)
    if accw==0 and bccw==0:
        if min(ap1[0],ap2[0])<max(ap1[0],ap2[0])<min(bp1[0],bp2[0])<max(bp1[0],bp2[0]):
            return 0
        if min(ap1[1],ap2[1])<max(ap1[1],ap2[1])<min(bp1[1],bp2[1])<max(bp1[1],bp2[1]):
            return 0
        if min(bp1[0],bp2[0])<max(bp1[0],bp2[0])<min(ap1[0],ap2[0])<max(ap1[0],ap2[0]):
            return 0
        if min(bp1[1],bp2[1])<max(bp1[1],bp2[1])<min(ap1[1],ap2[1])<max(ap1[1],ap2[1]):
            return 0
        return 1
    elif accw==0 or bccw==0:
        if accw>0 or bccw>0:
            return 0
        return 1
    elif accw<0 and bccw<0:
        return 1
    return 0
        
def find_root(x):
    if x==parent[x]:
        return x
    else:
        parent[x]=find_root(parent[x])
        return find_root(parent[x])

def union(x,y):
    x=find_root(x)
    y=find_root(y)
    if x!=y:
        parent[x]=y

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if find_root(i)!=find_root(j):
            if intersect(i,j)==1:
                union(i,j)

for i in range(N):
    parentcnt[parent[find_root(i)]]+=1

groupcnt=0
maxgroup=0
for i in range(N):
    if parentcnt[i]!=0:
        groupcnt+=1
        if parentcnt[i]>maxgroup:
            maxgroup=parentcnt[i]

print(groupcnt)
print(maxgroup)

먼저 ccw(a,b,c)함수는 a,b,c가 각각 점의 위치를 [x,y]형태로 주어졌을 때 선분 ab와 ac의 외적값을 반환한다. 외적값은 ab와 ac 두 벡터가 반시계 방향이라면 양수, 시계 방향이라면 음수를 반환한다. 그리고 intersect(a,b)함수는 a번째 선분과 b번째 선분이 교차하는지 판단한다. 선분 교차 판정 알고리즘은 먼저 선분 a에대하여 b의 양 끝점을 ccw해준다 그 두 값을 곱한것을 accw로 정한다. 만약 b의 양 끝점이 선분 a가 향하는 방향의 다른 방향 (왼쪽,오른쪽)에 있다면 accw는 음수가 나오게 된다. 반대로 선분 b에대하여 선분a의 양 끝점을 ccw해주고 곱한 값을 bccw로 정한다.

 

accw가 음수라는 것은 반대로 말하면 선분a를 연장해 직선으로 만들었을때 직선a가 선분b의 양 끝점 사이를 지나므로 선분b를 무조건 가로지른다는 것이다. 반대로 bccw가 음수라는 것은 직선b가 선분a를 무조건 가로지른다는 것이다. 그러므로 accw가 음수, bccw가 음수이면 두 선분은 무조건 가로지르는 형태를 띠게 된다.

 

accw가 0인 경우는 선분a를 연장한 직선 a위에 b의 끝점중 하나가 존재한다는 뜻이다. bccw가 0인 경우는 직선b 위에 a의 끝점중 하나가 존재한다는 뜻이다. 만약 accw,bccw 모두 0이라면 선분 a와 선분 b는 한 직선 위에 있다는 뜻이다. 한 직선위에 있을때 교차하는 경우는 겹치는경우, 포함하는 경우 모두를 생각해야 한다. 이를 판단하는 것은 생각보다 복잡하기에 반대로 교차하지 않는 경우를 생각했다.

 

먼저 수평선 상에 두 선분이 교차하지 않으려면 선분a:1-2 선분b:3-4 이렇게 연결되면 교차하지 않는다. 선분a의 두점이 a1<a2이고 선분b의 두점이 b1<b2라면 a1<a2<b1<b2순서로 놓이거나 b1<b2<a1<a2순서로 놓이면 두 선분이 교차하지 않게 된다. 좌표평면 위에서는 x축,y축 모두 이 조건을 사용해주면 교차하지 않는 선분들을 가려 낼 수 있다.

 

다음 문제는 accw, bccw중 하나만 0인 경우이다. accw가 0인 경우, bccw가 음수이면 선분 b는 선분 a가운데를 스치듯 지나가게 된다. 반대로 bccw가 양수이면 선분 b는 선분 a의 범위 바깥에서 직선a를 스치듯 지나가게 되므로 bccw가 양수인 경우를 제외해주면 된다. 반대로 bccw==0, accw>0 인 경우도 제외해 주면 선분 교차 판정은 끝나게 된다.

 

다음으로 각 선분들을 서로 교차 판정해 주고 교차한다면 union해 준다. 만약 두 선분들의 root가 같다면 두 선분은 이미 교차한 것이므로 교차 판정에서 제외한다. find와 union을 사용해 교차하는 그룹들을 나눌 수 있다.