만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 2162 선분 그룹

23 Jun 2021

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

2차원 평면상에 여러 선분들이 주어졌을 때 두 선분이 만나는 경우에는 같은 그룹에 속한다고 정의한다고 하자. 총 몇 개의 그룹으로 선분들이 이루어져 있는지 또 가장 크기가 큰 그룹의 선분의 갯수는 몇 개인지 구하는 문제이다.

먼저 선분들간에 충돌 여부를 확인해줘야하기 때문에 ccw알고리즘이 활용된다는 것을 짐작할 수 있다. 그런데 선분들을 그룹에 포함시키는 일을 어떻게 처리해줘야 할까? 바로 union-find 알고리즘을 활용할 것이다. 만약 두 선분이 충돌한다면 두 선분을 union 시켜주는 행위를 통해 하나의 그룹으로 만들 수 있다.

단 구현자체는 간단한 알고리즘이지만 한가지 union-find 알고리즘에 변형을 시켜줘야한다. 가장 크기가 큰 그룹의 선분의 갯수를 파악해줘야 하기 때문에 각각의 집합마다 포함된 선분의 갯수를 저장해주도록 하자. 또한 마지막에 그룹의 갯수를 파악하기 위해서 그룹의 root에 해당하는 선분마다 표시를 해줘서 root인 선분이 몇개 있는지 세는 것으로 그룹의 갯수를 파악할 수 있도록 구현하였다.

func ccw(x1: Int, x2: Int, x3: Int, y1: Int, y2: Int, y3: Int) -> Int {
    let result = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
    if result > 0 {
        return 1
    }
    else if result == 0 {
        return 0
    }
    else {
        return -1
    }
}

func meet(x1: Int, x2: Int, x3: Int, x4: Int, y1: Int, y2: Int, y3: Int, y4: Int) -> Bool {
    var A = (x1, y1), B = (x2, y2), C = (x3, y3), D = (x4, y4)
    let ABC = ccw(x1: x1, x2: x2, x3: x3, y1: y1, y2: y2, y3: y3)
    let ABD = ccw(x1: x1, x2: x2, x3: x4, y1: y1, y2: y2, y3: y4)
    let CDA = ccw(x1: x3, x2: x4, x3: x1, y1: y3, y2: y4, y3: y1)
    let CDB = ccw(x1: x3, x2: x4, x3: x2, y1: y3, y2: y4, y3: y2)
    if ABC == 0 && ABD == 0 {
        if A > B {
            swap(&A, &B)
        }
        if C > D {
            swap(&C, &D)
        }
        if B >= C && D >= A {
            return true
        }
        else {
            return false
        }
    }
    else if ABC*ABD <= 0 && CDA*CDB <= 0 {
        return true
    }
    else {
        return false
    }
}

struct DisjointSet {
    var arr:[Int]
    var child:[Int]
    var isRoot:[Bool]
    var setCount:Int {
        get {
            var tmp = 0
            for i in 1...isRoot.count-1 {
                if isRoot[i] {
                    tmp += 1
                }
            }
            return tmp
        }
    }
    var maxSet:Int? {
        return child.max()
    }
    init(_ n: Int) {
        arr = [Int](0...n)
        child = Array(repeating: 1, count: n+1)
        isRoot = Array(repeating: true, count: n+1)
    }
    mutating func findRoot(_ n: Int) -> Int {
        if arr[n] == n {
            return n
        }
        else {
            let root = findRoot(arr[n])
            arr[n] = root
            return root
        }
    }
    mutating func union(_ a: Int, _ b: Int) {
        let rootA = findRoot(a), rootB = findRoot(b)
        if rootA == rootB {
            return
        }
        else if rootB > rootA {
            arr[rootB] = rootA
            child[rootA] += child[rootB]
            isRoot[rootB] = false
        }
        else {
            arr[rootA] = rootB
            child[rootB] += child[rootA]
            isRoot[rootA] = false
        }
    }
}

let n = Int(readLine()!)!
var line:[(x1:Int, y1:Int, x2:Int, y2:Int)] = [(0, 0, 0, 0)]
var disjoint = DisjointSet(n)
for _ in 1...n {
    let l = readLine()!.split(separator: " ").map{Int(String($0))!}
    line.append((x1:l[0], y1:l[1], x2:l[2], y2:l[3]))
}
for i in 1..<n {
    for j in i+1...n {
        let line1 = line[i], line2 = line[j]
        if meet(x1: line1.x1, x2: line1.x2, x3: line2.x1, x4: line2.x2, y1: line1.y1, y2: line1.y2, y3: line2.y1, y4: line2.y2) {
            disjoint.union(i, j)
        }
    }
}

print(disjoint.setCount)
print(disjoint.maxSet!)

Related posts