[백준 2162] 선분 그룹 (Kotlin)

🏆 문제 난이도
- Platinum V

🔗 문제 링크
https://www.acmicpc.net/problem/2162

📝 문제 분석 & 접근

이 문제는 두 가지 개념적 큰 흐름이 있습니다.

1. 두 선분이 만나는지 판별하는 선분 교차 판정
2. 만나는 선분을 그룹으로 묶는 Union-Find

코드의 전체적인 흐름은 아래와 같이 설계할 수 있습니다

1. 모든 선분 쌍에 대해 교차하는지 검사하기
2. 교차한다면 Union-Find로 두 선분을 같은 그룹으로 합치기
3. 모든 검사가 끝나고, Union-Find에 남아있는 그룹의 총 개수와 가장 큰 그룹의 크기 세기

---

✨ 핵심 아이디어

1. 선분 교차 판정 (CCW 알고리즘)

두 선분이 교차하는지 판별하는 가장 대중적(?)인 방법은 CCW(Counter-Clockwise) 알고리즘입니다.

 

CCW는 세 점의 방향 관계를 알려주는 함수입니다.

세 점 P1, P2, P3가 주어졌을 때, P1 -> P2 -> P3 순서로 꺾이는 방향이 반시계 방향이면 양수, 시계 방향이면 음수, 일직선상이면 0을 반환합니다.

이 CCW를 이용해서 두 선분 AB와 CD의 교차를 판별하는 원리는 다음과 같습니다.

1. 선분 AB를 기준으로 점 C와 점 D가 서로 반대편에 있어야 한다.
   • CCW(A, B, C)와 CCW(A, B, D)의 부호가 달라야 함. 즉, CCW(A, B, C) * CCW(A, B, D) <= 0
2. 선분 CD를 기준으로 점 A와 점 B가 서로 반대편에 있어야 한다.
   • CCW(C, D, A)와 CCW(C, D, B)의 부호가 달라야 함. 즉, CCW(C, D, A) * CCW(C, D, B) <= 0

이 두 가지 조건을 동시에 만족하면 두 선분은 교차합니다!

단, 네 점 모두 일직선 위에 있는 특수 케이스는 따로 다뤄줘야 합니다.

 

2. 그룹 묶기 (Union-Find)

Union-Find 알고리즘은 각 원소가 어떤 집합에 속해있는지 관리하는 알고리즘입니다.

 

• parent 배열: 각 원소의 부모 노드를 저장합니다. 루트 노드는 자기 자신을 가리키거나, 특별한 값(코드에서는 음수)을 가집니다.
• find(a): 원소 a가 속한 집합의 대표(루트 노드)를 찾아 반환합니다. 경로 압축(Path Compression) 최적화를 통해 매우 빠르게 동작합니다.
• union(a, b): a와 b가 속한 두 집합을 하나로 합칩니다. 이 문제에서는 두 선분이 교차할 때 호출하게 됩니다.

 

저는 이 문제에서 Union-Find를 아래와 같이 사용했습니다.

코드에 대한 간략한 설명이니 코드를 같이 보며 확인해주세요.

• N개의 선분은 처음에는 각각 별개의 그룹(총 N개)으로 시작합니다.
• parent 배열의 인덱스는 선분의 번호를 의미합니다.
• parent[i]가 음수이면, i는 그룹의 루트 노드이고, abs(parent[i])는 그 그룹에 속한 선분의 개수를 의미하도록 구현했습니다.
• 선분 i와 j가 교차하면 union(i, j)를 호출해서 같은 그룹으로 만들어줍니다.

---

💻 코드

lateinit var parent: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine()!!.toInt()
    parent = IntArray(n){ -1 }
    val lines = Array(n){
        val(a, b, c, d) = readLine()!!.split(" ").map { it.toInt() }
        Line(a, b, c, d)
    }

    // 선분 쌍에 대해서 교차 검사 및 그룹 합치기 로직
    for (i in 0 until n) {
        for (j in i + 1 until n) {
            if(lines[i].intersection(lines[j])) union(i, j)
        }
    }

    var count = 0 // 그룹 수
    var min = 0 // 가장 큰 그룸 크기
    repeat(n) {
        if(parent[it] < 0){ // 루트 노드인 경우에
            count++
            if(parent[it] < min) min = parent[it] // 그룹 크기 갱신
        }
    }
    println("${count}\n${-min}")
}

fun union(a: Int, b: Int) {
    val a = find(a)
    val b = find(b)
    if(a == b) return // 이미 유니온

    // 아래부터는 유니온이 아닌 경우임
    val root= if(parent[a] < parent[b]) a else b // 더 큰 집합을 root로 가짐
    val sibling = if(parent[a] < parent[b]) b else a // 작은 집합은 sibling

    parent[root] += parent[sibling] // 새로운 집합의 크기
    parent[sibling] = root // sibling은 더이상 root가 아니므로, union한 친구의 root를 걸어줌.
}

fun find(a: Int): Int {
    if(parent[a] < 0) return a // 초기 상태일 경우
    parent[a] = find(parent[a])
    return parent[a]
}

data class Point(val x: Int, val y: Int) : Comparable<Point> {
    // comparable을 사용해서 각 Point들이 X가 작은 점 -> 큰 점 순으로 오름차순,
    // X가 같다면 Y가 작은 점 -> 큰 점 순으로 오름차순 순으로 정렬해준다.
    // 이는 ccw를 사용할 때, 더 큰 점이 뭔지 한번 더 체크하지 않기 위함임.
    override fun compareTo(other: Point): Int {
        return if(this.x == other.x) this.y - other.y else this.x - other.x
    }
}

class Line(p1: Point, p2: Point) {
    val a: Point
    val b: Point

    constructor(x1: Int, y1: Int, x2: Int, y2: Int) : this(Point(x1, y1), Point(x2, y2))

    init {
        if (p1 <= p2) {
            a = p1
            b = p2
        } else {
            a = p2
            b = p1
        }
    }

    // 선분 교차 판정
    fun intersection(other: Line): Boolean {
        val r1 = ccw(this.a, this.b, other.a) * ccw(this.a, this.b, other.b)
        val r2 = ccw(other.a, other.b, this.a) * ccw(other.a, other.b, this.b)
        if(r1 == 0 && r2 == 0) return (this.a <= other.b) && (other.a <= this.b)
        return r1 <= 0 && r2 <= 0
    }
}

fun ccw(p1: Point, p2: Point, p3: Point): Int {
    val result = (p1.x.toLong() * p2.y + p2.x.toLong() * p3.y + p3.x.toLong() * p1.y) -
            (p2.x.toLong() * p1.y + p3.x.toLong() * p2.y + p1.x.toLong() * p3.y)
    return when {
        result > 0 -> 1
        result < 0 -> -1
        else -> 0
    }
}