[백준] 4386번 별자리 만들기 [Swift]

문제 링크

4386번: 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

문제 풀이

이 문제는 무방향 그래프에서 가중치가 존재하는 그래프에서 최소한의 가중치로 모든 정점을 연결하는 방법을 찾는 최소 스패닝 트리 문제입니다.

하지만 이 문제에는 가중치는 주어지지 않았고 별들의 위치가 2차원으로 주어져있는 것을 사용하여 별 사이의 거리를 가중치로 직접 구해야 하는 문제였습니다.

별의 개수가 100개 밖에 되지 않아 저는 그냥 모든 별 사이의 거리를 구하고 거리를 기준으로 정렬했습니다.

그런 뒤 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어 주면 답이 나오게 됩니다!

 

소스 코드

import Foundation

func solution(){
    let n = Int(readLine()!)!
    var stars: [[Double]] = [[Double]]()
    var parent = Array(0..<n)
    var distanceData: [(Int,Int,Double)] = []
    var lines: Int = 0
    var result: Double = 0
    
    func find(_ index : Int) -> Int{
        if parent[index] == index {
            return index
        } else {
            parent[index] = find(parent[index])
            return parent[index]
        }
    }
    
    func union(_ a: Int, _ b : Int){
        let p1 = find(a)
        let p2 = find(b)
        if p1 < p2 {
            parent[p2] = p1
        } else {
            parent[p1] = p2
        }
    }
    
    for _ in 0..<n {
        let starData = readLine()!.split(separator: " ").map({Double(String($0))!})
        stars.append(starData)
    }
    
    // 별 사이의 거리를 직접 구해준다.
    for i in 0..<stars.count{
        for j in i+1..<stars.count{
            let distance = sqrt(pow((stars[i][0] - stars[j][0]), 2) + pow((stars[i][1] - stars[j][1]),2))
            distanceData.append((i,j,distance))
        }
    }
    
    // 별 사이의 거리를 기준으로 오름차순 정렬한다.
    distanceData.sort { (a, b) -> Bool in
        return a.2 < b.2
    }
    
    // 크루스칼 알고리즘 수행
    for index in 0..<distanceData.count{
        if lines == n - 1{
            break
        }
        if find(distanceData[index].0) != find(distanceData[index].1){
            result += distanceData[index].2
            lines += 1
            union(distanceData[index].0, distanceData[index].1)
        }
    }
    
    print(round(result * 100) / 100)
    
}

solution()