[Swift] BOJ 1647 도시 분할 계획

BOJ 1647 도시 분할 계획

 

✅ 이 문제는 살펴 보아야할 것들이 조금 많다.

우선 나동빈 책에 있는 대표적인 유형이다.

 

크루스칼 알고리즘을 사용하면 쉽게 풀 수 있었지만, Swift를 사용하는 내게 시간초과라는 결과를 받음.

 

✅ 내가 처음에 푼 알고리즘. (시간초과)

        let firstLine = readLine()!.split(separator: " ").map { Int($0)! }

        var parent = Array(0...firstLine[0]) // 부모노드 생성
        for i in 0...firstLine[0] {
            parent[i] = i
        }
//        print(parent)

        var edges = [(Int, Int, Int)]() // 시작, 끝, 비용
        for _ in 0..<firstLine[1] {
            let i = readLine()!.split(separator: " ").map { Int($0)! }
            edges.append((i[0], i[1], i[2]))
        }
        edges.sort { $0.2 < $1.2 }
//        print(edges)

        var result = 0
        var last = 0
        for edge in edges {

            let a = find(parent: &parent, i: edge.1)
            let b = find(parent: &parent, i: edge.0)

//            print("👉 edge \(edge) a: \(a) b: \(b)")
            if a != b { // a와 b가 다르다면 사이클이 발생하지 않는다는 의미
                result += edge.2
                last = edge.2
//                print("✅ a: \(a) b: \(b) cost \(edge.2) result \(result)")
                union(parent: &parent, start: edge.0, end: edge.1)
            }
        }
        // 2개로 분할하는데, 그냥 가장 긴 경우 빼면 된다.
        print(result - last)

        // 루트노드를 찾습니다.
        func find(parent: inout [Int], i: Int) -> Int {
            if parent[i] == i { return i } // 같으면 루트 노드가 없다는 의미
            else {
                let answer = find(parent: &parent, i: parent[i])
                return answer
            }
        }

        // inout을 사용해서 & 처럼 사용
        func union(parent: inout [Int], start: Int, end: Int) {
            let num1 = find(parent: &parent, i: start)
            let num2 = find(parent: &parent, i: end)

            // 어찌되었든 합쳐야 함. 더 작은 수가 root로 전부 세팅
            if start < end {
                parent[num2] = num1
            } else {
                parent[num1] = num2
            }
        }

 

✅ 최종 풀이 (통과)

 - 다른 사람의 알고리즘을  빌림. 

내 시간초과 코드와 비교하면 tuple을 사용했지만, 입력 후 다시 정렬하고 이런 과정에서 시간 손해를 많이 보는 듯 싶다.

다른 사람의 경우 readLine을 사용하면 swfit는 데이터가 많아지면 급격하게 느려진다고 하는데 이도 참고하자.

        import Foundation
        let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
        
        var graph: [[Int]] = []
        // 2차원 배열로 세팅함.
        for _ in 0..<firstLine[1] {
            graph.append(readLine()!.split(separator: " ").map { Int($0)! })
        }
        
        
        var a = kruskalDivide(graph: &graph, edgeCount: firstLine[0])
        print(a)


func kruskalDivide(graph: inout [[Int]], edgeCount: Int) -> Int {
    // 부모 노드를 찾는 함수
    func getParent(_ array: inout [Int], _ index: Int) -> Int {
        
        if array[index] == index {
            return index
        } else {
            array[index] = getParent(&array, array[index])
            return array[index]
        }
    }
    
    
    // 부모 노드를 합치는 함수
    func unionParent( _ array: inout [Int], _ a: Int, _ b: Int) {
        let num1 = getParent(&array, a)
        let num2 = getParent(&array, b)
        
        if a < b {
            array[num2] = num1
        } else {
            array[num1] = num2
        }
    }
    
    var result: Int = 0
    var parentNodeTable: [Int] = []
    
    // 추가된 간선 수
    var lines: Int = 0
    
    // 간선을 가중치 순으로 나열 - 오름차순 정렬
    graph.sort { (a, b) -> Bool in
        return a[2] < b[2]
    }
    
    // 부모 테이블 초기 셋팅
    for i in 0...edgeCount{
        parentNodeTable.append(i)
    }
    
    var last = 0
    for index in 0..<graph.count{
        
        // 추가된 간선수가 정점 수 - 1이면 반복 중단
        if lines == edgeCount - 1{ break }
        
        // 만약 부모가 다르다면 사이클을 발생하지 않기 때문에 간선 추가
        if getParent(&parentNodeTable, graph[index][0]) != getParent(&parentNodeTable, graph[index][1]) {
            result += graph[index][2]
            last = graph[index][2]
            lines += 1
            
            // 부모 노드 합침
            unionParent(&parentNodeTable, graph[index][0], graph[index][1])
        }
    }
    
    return result - last
}

이 알고리즘은 아래 블로그에서 참고하여 푼 알고리즘이다. 

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

1647번: 도시 분할 계획

 

 

 

✅ 다른 풀이 - 시간복잡도는 제일 적지만, 활용하기가 힘들 것 같음.

도시분할계획 - 백준 1647 - swift

 

import Foundation
// 👍 https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88 
// 라이노님의 빠른 readLine() 
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시

        while now != 10
            && now != 32 && now != 0 {
                str += String(bytes: [now], encoding: .ascii)!
                now = read()
        }

        return str
    }
}



let file = FileIO()


let N = file.readInt()
let M = file.readInt()

var array = [[Int]]()
for _ in 0..<M {
    let x1 = file.readInt()
    let x2 = file.readInt()
    let cost = file.readInt()
    array.append([x1,x2,cost])
}




var costs = 0
var maxCost = 0
var parent = Array(0...N)

func union(_ x : Int , _ y : Int ) {
    let parentA = find(x)
    let parentB = find(y)
    
    parent[parentB] = parentA
}
func find(_ x : Int ) -> Int {
    if parent[x] == x { return x }
    else { parent[x] = find(parent[x])}
    return parent[x]
}


array.sort(by : {$0[2] < $1[2]})

for node in array {
    let pX = find(node[0]), pY = find(node[1])
    if pX != pY {
        union(node[0], node[1])
        costs += node[2]
        maxCost = max(maxCost,node[2])
    }
}

print(costs - maxCost)​

 

✅ 결과

먼저 제출한 순서로

 내코드 (시간초과)

 내코드 (틀렸습니다.) -> 코드 입력 잘못함.

 내 포스팅 3번째 코드 (제일 빠름)

 내 포스팅 중간 코드 

통과