[BOJ] 2162번 : 선분 그룹(경로 압축, CCW)

목차

접근

2차원 평면상에 존재하는 `N`개의 선분들의 교차를 체크하고, 만약 교차하거나 만난다면 하나의 선분 그룹으로 속한다고 정의하고, 그룹의 수와 가장 큰 그룹에 속한 선분의 갯수를 찾는 문제.

 

선분의 교차를 체크하는 방법론은 예전에 선분 교차 문제를 풀어봤던 기억이 있어서 CCW(Counter Clock Wise)알고리즘을 이용해서 접근했다.

CCW 알고리즘은 외적을 이용해서 선분의 교차를 판정하는 방법론이다.

외적에 대한 설명은

[BallPen님의 블로그]: 외적 - 벡터끼리 곱하여 벡터가 되는 계산법

 이 블로그에 아주 자세히 나와있다. 

나는 참고해서 설명하겠다.

 

외적

아래는 외적의 식이다. 

 

$ \vec{A} \times \vec{B} = ABsin\theta \hat{n}$

$ \hat{n} $ 은 두 벡터로 만들어지는 평면에 수직인 단위벡터이다.

 

위의 식을 수학적으로 계산해보자.

위의 블로그에선 성분법과 행렬표현법 두가지 모두 계산과정을 제공하니, 더 자세히 궁금하면 한번 봐보자.

나는 성분법으로 푸는 풀이만 옮겨서 적겠다.

 

$ \vec{A} \times \vec{B} = \\ (A_x\hat{x} + A_y\hat{y}+A_z\hat{z}) \times (B_x\hat{x}+B_y\hat{y}+B_z\hat{z}) \\ = A_xB_x(\hat{x}\times \hat{x}) + A_xB_y(\hat{x} \times \hat{y}) + A_xB_z(\color{red}{\hat{x} \times \hat{z}}) \\ + A_yB_x(\color{red}{\hat{y} \times \hat{x}}) + A_yB_y(\hat{y} \times \hat{y}) + A_yB_z(\hat{y} \times \hat{z})\\ + A_zB_x(\hat{z} \times \hat{x}) + A_zB_y(\color{red}{\hat{z} \times \hat{y}}) + A_zB_z(\hat{z} \times \hat{z})  $

 

같은 방향의 벡터간의 외적값은 0이니까 신경쓰지 않아도 되고, 빨간색으로 표시된 단위벡터들의 외적을 주의깊게 봐보자.

 

x 외적 y

위의 그림은 수직인 벡터의 방향을 결정하는데 이해하기 쉽도록 직접 그려보았다.

외적은 교환법칙이 성립하지 않기때문에, 항상 순서를 맞춰서 계산하는게 중요하다.

저 그림은 $ \vec{x} \times \vec{y} $ 를 표현한 것인데, 만약 $ A \times B $ 순서로 벡터의 외적을 계산한다면, 벡터 `A`는 검지손가락에 벡터 `B`는 중지손가락에 맞춰서 놓고 엄지손가락이 가리키는 방향이 두 외적에 수직인 벡터의 방향이 된다.

$ \vec{x} \times \vec{y} $를 예시로 하면, 단위벡터 `z`가 나오게 될 것이다.

 

그렇다면, 위의 $\vec{x} \times \vec{z} $ 는 수직인 벡터는 어떻게 될까? 한번 손가락을 펼쳐서 생각해보자.

펼쳐보았는가? 바로 $-\vec{y}$ 가 나오게 된다. 

$ \vec{y} \times \vec{x} $ 는 어떻게 될까? 바로 $ -\vec{z} $ 가 나오게 된다.

$ \vec{z} \times \vec{y} $ 는 $ -\vec{x} $ 가 나오게 된다.

이 연산결과를 이용해서 식의 전개를 계속 수행해보자.

 

$ \vec{A} \times \vec{B} \\ = A_xB_x(1 \cdot 1 \cdot sin0^\circ) + A_xB_y(1 \cdot 1 \cdot sin90^\circ \vec{z}) + A_xB_z(1 \cdot 1 \cdot sin90^\circ (\color{red}{-\vec{y}})) \\ + A_yB_x(1 \cdot 1 \cdot sin90^\circ (\color{red}{-\vec{z}})) + A_yB_y(1 \cdot 1 \cdot sin0^\circ) + A_zB_z(1 \cdot 1 \cdot sin90^\circ \vec{x})  \\ + A_zB_x(1 \cdot 1 \cdot sin90^\circ \vec{y}) + A_zB_y(1 \cdot 1 \cdot sin90^\circ (\color{red}{-\vec{x}})) + A_zB_z(1 \cdot 1 \cdot sin0^\circ) \\ = 0 + A_xB_y\vec{z} + A_xB_z(-\vec{y}) \\ + A_yB_x(-\vec{z}) + 0 + A_yB_z\vec{x} \\ + A_zB_x\vec{y} + A_zB_y(-\vec{x}) + 0 \\ = (A_yB_z - A_zB_y)\vec{x} + (A_zB_x - A_xB_z)\vec{y} + (A_xB_y - A_yB_x)\vec{z} $

 

이렇게 외적에 대한 연산을 수행할 수 있다.

 

근데 우리는 평면인데 무슨 3차원 소리냐.

외적이 3차원에서 쓰이는걸 어떡해...

위의 성분법에서 2차원 평면은 z값을 0으로 만들어주고 연산을 수행하면 된다.

 

$ \vec{A} \times \vec{B} = (A_x\vec{x} + A_y\vec{y}) \times (B_x\vec{x} + B_y\vec{y}) \\ = A_xB_x(\vec{x} \times \vec{x}) + A_xB_y(\vec{x} \times \vec{y}) \\ + A_yB_x(\vec{y} \times \vec{x}) + A_yB_y(\vec{y} \times \vec{y}) \\ = A_xB_x(1 \cdot 1 \cdot sin0^\circ) + A_xB_y(1 \cdot 1 \cdot sin90^\circ \vec{z}) \\ + A_yB_x(1 \cdot 1 \cdot sin90^\circ (-\vec{z})) + A_yB_y(1 \cdot 1 \cdot sin0^\circ) \\ = A_xB_y\vec{z} + A_yB_x(-\vec{z}) = (A_xB_y - A_yB_x)\vec{z} $ 

 

결론적으로 2차원 평면에서의 외적을 이용하여 나온 결과인 z성분 $ A_xB_y - A_yB_x $ 값은 외적의 부호를 결정하는 역할을 하게 된다.

 

벡터로 표현이 되어있기 때문에, 각 벡터의 예시를 들어서 한번 z성분의 값을 풀어써보자.

$ a = (a_x, a_y), b = (b_x, b_y), c = (c_x, c_y) \\ \vec{A} = \vec{ab} = (b_x-a_x, b_y-a_y) \\ \vec{B} = \vec{ac} = (c_x-a_x, c_y-a_y) \\ A_xB_y = (b_x-a_x)*(c_y-a_y) , A_yB_x = (b_y-a_y)*(c_x-a_x) $

$ \therefore A_xB_y - A_yB_x = (b_x-a_x)*(c_y-a_y) - (b_y-a_y)*(c_x-a_x) \\ = a_xb_y + b_xc_y + c_xa_y -a_yb_x - b_yc_x - c_y a_x$

 

이렇게 정리한 저 모양이 바로 그 신발끈 공식의 결과다.

직접 그리고 있었다...신발끈 공식

이 결과값의 부호가 왜 중요한걸까?

위에서 설명한 외적의 결과값은 외적의 순서에 따라 검지와 중지를 어디에 놓냐에 따라 달라질 수 있었다. 

일반적인 $ \vec{x} \times \vec{y} $ 는 $ \vec{z} $가 나왔었다. 그럼 반대로 $ \vec{y} \times \vec{x} $를 하면 어떻게 될까? 바로 $ -\vec{z} $ 가 된다.(이건 검지랑 중지를 각각의 축에 맞춰서 한번 놓고 생각해봐라..)

 

이 내용을 이렇게 해석해볼 수 있을 것 같다.

A를 기준으로 시계방향(빨강), 반시계방향(파랑) 에 있는 벡터들에 대한 외적값

$ \vec{A} \times \vec{B} $ 의 계산에서 항상 $\vec{A}$ 를 검지에 놓고, 시계 방향과 반시계 방향에 있는 벡터들을 생각해보자. 오른손을 뒤집어가며, 수직으로 나오는 벡터의 방향이 어떻게 되는지 위의 그림에서 보면, 반시계방향의 벡터는 z축의 +방향(`T > 0`), 시계방향의 벡터는 z축의 -방향(`T^' < 0`) 으로 나오게 된다.

 

CCW 알고리즘은 이 벡터간의 방향성에 대한 내용을 이용해서, 선분의 교차를 판단한다.

(여담이지만, 진짜 지금까지 써왔던것중에 가장 공들여서 포스트를 작성하고 있다. 이유는 딱히 없지만, 외적과 CCW알고리즘에 대해서 한번 정리하고싶기도 했고, 그냥 쉽지 않은 알고리즘이라 정리해두면 다른 사람들에게 도움이 많이 될 것 같아서이다..)

이제 진짜 CCW 알고리즘을 이용한 선분교차판정으로 들어가보자.

---

CCW(Counter Clock Wise) - 선분교차판정

기본적인 전제는 아래와 같다.

• 각각의 선분에 대한 벡터의 외적값의 곱이 0보다 작으면 둘은 교차한다고 볼 수 있다.

위는 그냥 정말 '기본적인' 전제이다. 

교차하는 선분간의 상태를 보자.

AB, CD 선분간의 교차상태

선분 AB와 선분 CD가 있다고 할 때, 선분 AB를 벡터로 인식하고 상대 선분의 양 끝 점까지를 벡터로 생각해보자. 그렇다면 $ \vec{AB} $를 기준으로 $ \vec{AC} $ 는 반시계방향, $ \vec{AD} $는 시계방향에 위치하게 된다.

그러면 $ \vec{AB} \times \vec{AC} $의 부호는 +가 나올 것이고, $ \vec{AB} \times \vec{AD} $의 부호는 -가 나올 것이다. 따라서 교차상태의 선분의 외적값의 곱은 0보다 작아질 것이다.

 

그럼 아래와 같은 케이스는 어떨까?

교차하지 않는 예외케이스

위와 똑같이 외적값의 곱의 결과가 0보다 작게 나올 것이지만, 두 선분은 교차하지 않을 것이다.

그래서 이 케이스에 대한 예외처리를 해야한다.

예외처리에 대해 생각해보자.

우리는 $ \vec{AB} $에 대해서만 선분 CD로의 시계방향과 반시계 방향을 판단했다.

근데 이 예외는 $ \vec{AB} $를 기준으로는 시계방향, 반시계방향을 만족하지만, $ \vec{CD} $를 기준으로 선분 AB를 보면 문제가 생긴다.

이런 예외 케이스의 경우는 $ \vec{CD} $를 기준으로, $ \vec{CA} $ 와 $ \vec{CB} $ 모두 시계방향에 있다. 

그렇기 때문에 정상적인 교차형태라고 한다면, $ \vec{AB} $ 와 $ \vec{CD} $ 를 각각 기준으로 하여, 상대 선분에 대한 외적값의 곱이 0보다 작게 나오도록 하는 케이스를 찾아야한다. 결론적으로는 아래와 같은 케이스를 찾으면 선분의 교차형태를 정확하게 파악할 수 있다는 것이다.

외적( AB, AC) * 외적(AB, AD) < 0 and 외적(CD, CA) * 외적(CD, CB) < 0

 

아 또 여기서 설명하지 않은게 있는데, 교차는 이런식이 아닌 두 선분이 나란한 방향으로 포개졌을 때도 교차한다고 볼 수 있다.

그것에 대한 예외 케이스는 너무 간단하기 때문에 굳이 수식이 필요한 내용에선 설명하지 않겠다.(아래 문제 풀이 코드에 적어둔 내용을 보고 직접 판단해보자. 같은 방향의 벡터끼리라면 외적값이 0이 나올것. -> 선분간의 상대적인 위치관계만 파악하면 된다.)

해결

CCW를 이용해서 모든 선분간의 교차관계를 파악해주고, Union-Find를 이용해서 루트노드가 작은쪽으로 교차 집합을 합쳐주었다.

 

이렇게 해결했을 때, 계속 틀리는 부분이 생겨서 질문게시판을 찾아보던 중 Union-Find 알고리즘에서 Union 알고리즘은 집합의 대표끼리 합치는 작업을 수행할뿐, 합쳐지는 요소의 하위는 바뀌지 않고 이전 요소를 가리키고 있다라는 문제점이 있다는 것을 보았다. 그래서 마지막에 각각의 모든 요소들에 대해서 Find 작업을 한번 더 수행해줌으로써, 전체의 루트노드를 한번 더 갱신해줌으로 문제를 맞추게 되었다.

Union-Find 관한 설명은 아래 아티클을 참고하자.

2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal)

 

코드

import sys

input = sys.stdin.readline

N = int(input())
coords = []
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    coords.append((x1, y1, x2, y2))
    
def CCW(line_1, line_2):
    x1, y1, x2, y2 = line_1 # A(x1, y1), B(x2, y2)
    x3, y3, x4, y4 = line_2 # C(x3, y3), D(x4, y4)
    
    # (A, B, C), (A, B, D) 와 (C, D, A), (C, D, B)의 외적의 부호가 서로 다르면 교차한다.
    outer_product_1 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) # A, B, C 외적 : x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3)
    outer_product_2 = (x2-x1)*(y4-y1) - (y2-y1)*(x4-x1) # A, B, D 외적 : x1y2 + x2y4 + x4y1 - (x2y1 + x4y2 + x1y4)
    outer_product_3 = (x4-x3)*(y1-y3) - (y4-y3)*(x1-x3) # C, D, A 외적 : x3y4 + x4y1 + x1y3 - (x4y3 + x1y4 + x3y1)
    outer_product_4 = (x4-x3)*(y2-y3) - (y4-y3)*(x2-x3) # C, D, B 외적 : x3y4 + x4y2 + x2y3 - (x4y3 + x2y4 + x3y2)
    
    if outer_product_3 * outer_product_4 <= 0 and outer_product_1 * outer_product_2 <= 0:
        if outer_product_3*outer_product_4 == 0 and outer_product_1*outer_product_2 == 0: # 둘이 일직선이 되는 경우, 상대적인 위치를 비교하여 교차 판단
            max_a_b = (max(x1, x2), max(y1, y2))
            min_a_b = (min(x1, x2), min(y1, y2))
            max_c_d = (max(x3, x4), max(y3, y4))
            min_c_d = (min(x3, x4), min(y3, y4))
            
            if not((max_a_b[0] >= min_c_d[0] and max_a_b[1] >= min_c_d[1]) and (max_c_d[0] >= min_a_b[0] and max_c_d[1] >= min_a_b[1])):
                return False
            
        return True # line_1 , line_2 교차여부
    else:
        return False
    
    
cnt = [1] * N
parents = [i for i in range(N)]

def find(x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y: # 트리의 루트 노드가 같다면
        return # 넘어감
    else:
        if x < y: # 루트 노드가 작은쪽으로 몰아줌
            parents[y] = x
            cnt[x] += cnt[y]
        else:
            parents[x] = y
            cnt[y] += cnt[x]
            

for i in range(N):
    for j in range(i+1, N):
        if CCW(coords[i], coords[j]):
            union(i, j)
            
for i in range(N):
    parents[i] = find(parents[i])
            
print(len(set(parents)))
print(max(cnt))