[Python] 백준 2162번: 선분 그룹

https://www.acmicpc.net/problem/2162

2162번: 선분 그룹

 

import sys
input = sys.stdin.readline


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)


def is_two_lines_intersecting(line1, line2):
    x1, y1, x2, y2 = line1
    x3, y3, x4, y4 = line2

    mx1, my1 = min(x1, x2), min(y1, y2)
    mx2, my2 = max(x1, x2), max(y1, y2)
    mx3, my3 = min(x3, x4), min(y3, y4)
    mx4, my4 = max(x3, x4), max(y3, y4)

    ccw123 = ccw(x1, y1, x2, y2, x3, y3)
    ccw124 = ccw(x1, y1, x2, y2, x4, y4)
    ccw341 = ccw(x3, y3, x4, y4, x1, y1)
    ccw342 = ccw(x3, y3, x4, y4, x2, y2)

    if ccw123*ccw124 == 0 and ccw341*ccw342 == 0:
        if mx1 <= mx4 and mx3 <= mx2 and my1 <= my4 and my3 <= my2:
            return True
    else:
        if ccw123*ccw124 <= 0 and ccw341*ccw342 <= 0:
            return True

    return False


def findParent(x):
    if parents[x] == x:
        return x

    parents[x] = findParent(parents[x])
    return parents[x]


def union(x, y):
    px, py = findParent(x), findParent(y)

    if px < py:
        parents[py] = px
    else:
        parents[px] = py


if __name__ == '__main__':
    N = int(input())
    positions = [list(map(int, input().split())) for _ in range(N)]

    parents = [i for i in range(N)]

    for i in range(N-1):
        for j in range(i+1, N):
            # 선분이 교차할 시 두 그룹을 합친다.
            if is_two_lines_intersecting(positions[i], positions[j]):
                union(i, j)

    # parents를 통해 출력값을 얻는다.
    group_count = 0
    group_line_counts = [0]*N

    for i in range(N):
        # 자기 자신을 가리킨다 = 루트 노드
        if i == parents[i]:
            group_count += 1

        group_line_counts[findParent(i)] += 1

    print(group_count)
    print(max(group_line_counts))

 

ccw를 이용한 교차 판정 알고리즘과 Union-find 알고리즘을 알고 있다는 가정 하에 글을 작성하였다.

 

교차 판정 알고리즘 관련 링크:

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-17387%EB%B2%88-%EC%84%A0%EB%B6%84-%EA%B5%90%EC%B0%A8-2

[Python] 백준 17387번: 선분 교차 2

Union-find 관련 링크:

https://rccode.tistory.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Python-10775%EB%B2%88-%EA%B3%B5%ED%95%AD

[유니온 파인드] Python - 10775번, 공항

 

 

이중for문으로 모든(every) 선분에서 모든(every) 선분에 대해 교차판정을 해주며, 교차할 때 두 그룹을 합쳐준다.

 

이렇게 만들어진 parents를 기반으로 출력값을 얻을 수 있다.

먼저, x == parents[x]라는 조건문은 x가 루트인지를 체크하는 것과 같다. 예를 들어 예제 입력 1에서는 parents가 [0, 0, 0]으로 나오는데, 여기서 0번째 원소가 루트이다.

그리고 group_line_counts라는 리스트에 각 그룹에 선분이 몇 개 있는지를 카운트하여 저장해준다. 이 때 group_line_counts[i] += 1이 아니라 인덱스에 findParents(i)를 넣어주는 것에 유의하자.(parents가 0 1 1 3인 상태에서 0, 1번째 원소를 union한다고 하자. 그럼 parents는 0 0 1 3이 된다. 0 0 0 3이 아니다!)