1647 - swift

우리는 길 유지비의 합을 최소로 만들어야 한다. 그렇다면 유지비 촤르르륵 있는 배열을 유지비로 오름차순으로 정렬을 해놓고 낮은것부터 만약 노드 길이 없다면 생성해주고 맨 마지막꺼만  빼주면 그게 최소가 아닐까? 라고 생각을 하였다. 

//1647
let NM = readLine()!.split(separator: " ").map{Int($0)!}
let N = NM[0]
let M = NM[1]
var arr : [[Int]] = Array(Array(repeating: [], count: M))
for i in 0..<M{
    arr[i] = readLine()!.split(separator: " ").map{Int($0)!}
}
arr.sort{$0.last! < $1.last!} //짧은놈들먼저 연결을 해야 최소로 해줄수 있으므로
var answer : Set<Int> = []
var howmuch = 0
var last = 0

var parent = Array(repeating: 0, count: N+1)
for i in 0...N{
    parent[i] = i
}
func find_parent(parent : [Int], x : Int)->Int{ //특정 원소가 속한 집합을 찾는것이다.
    if(parent[x] != x){ // 만약 루트노드가 아니면 루트노드 찾을때까지 반복!
        var parent = find_parent(parent: parent, x: parent[x])
        return parent
    }
    else{
        return x
    }
}
func union(parent: inout [Int], a: Int, b:Int){   //parent가 let변수가 되면서 수정이 안되어서 inout으로.
    let num1 = find_parent(parent: parent, x: a)
    let num2 = find_parent(parent: parent, x: b)
    if a<b{
        parent[num2] = num1
    }else{
        parent[num1] = num2
    }
}
for edge in arr{
    if(find_parent(parent: parent, x: edge[0]) != find_parent(parent: parent, x: edge[1])){
        howmuch += edge[2]
        last = edge[2]
        union(parent: &parent, a: edge[0], b:   edge[1])
    }
}
print(howmuch - last)

물론 답은제대로 나오는데 실패다.. 왜? 시간초과ㅜㅠ

//1647
import Foundation
let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NM[0]
let M = NM[1]
var arr : [[Int]] = Array(Array(repeating: [], count: M))
for i in 0..<M{
    arr[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
}
arr.sort{$0.last! < $1.last!} //짧은놈들먼저 연결을 해야 최소로 해줄수 있으므로
var answer : Set<Int> = []
var howmuch = 0
var last = 0

var parent = Array(repeating: 0, count: N+1)
for i in 0...N{
    parent[i] = i
}
func find_parent(parent : inout [Int], x : Int)->Int{
    if(parent[x] != x){ //여기서 문제발견 만약 맨위로 올라갈라면 한단계씩 루트를 거쳐 올라가서 O(N) 그래서 inout으로 경로 단축
        parent[x] = find_parent(parent: &parent, x: parent[x])
        return parent[x]
    }
    else{
        return x
    }
}
func union(parent: inout [Int], a: Int, b:Int){   //parent가 let변수가 되면서 수정이 안되어서 inout으로.
    let num1 = find_parent(parent: &parent, x: a)
    let num2 = find_parent(parent: &parent, x: b)
    if a<b{
        parent[num2] = num1
    }else{
        parent[num1] = num2
    }
}
var lines : Int = 0 //간선수
for edge in arr{
    // 만약 추가된 간선수가 정점수 -1이면 끝
    if lines == N-1{
        break
    }
    if(find_parent(parent: &parent, x: edge[0]) != find_parent(parent: &parent, x: edge[1])){
        howmuch += edge[2]
        last = edge[2]
        union(parent: &parent, a: edge[0], b:   edge[1])
        lines+=1
    }
}
print(howmuch - last)

그래서 다음에는 find에서 한단계씩 위로 가는것이 아닌 시간을 줄여주기위해 inout으로 해주고 line은 정점수 - 1이면 충분하므로 중단조건을 걸어주었다. 하지만 여전히 시간초과.. 

//1647
import Foundation
let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NM[0]
let M = NM[1]
var arr : [[Int]] = []
for _ in 0..<M{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
arr.sort(by: {$0[2] < $1[2]}) //짧은놈들먼저 연결을 해야 최소로 해줄수 있으므로
var answer : Set<Int> = []
var howmuch = 0
var last = 0

var parent = Array(repeating: 0, count: N+1)
for i in 0...N{
    parent[i] = i
}
func find_parent(parent: inout [Int], x: Int) -> Int {
    if parent[x] != x {
        parent[x] = find_parent(parent: &parent, x: parent[x])
    }
    return parent[x]
}

func union(parent: inout [Int], a: Int, b:Int){   //parent가 let변수가 되면서 수정이 안되어서 inout으로.
    let num1 = find_parent(parent: &parent, x: a)
    let num2 = find_parent(parent: &parent, x: b)
    if a<b{
        parent[num2] = num1
    }else{
        parent[num1] = num2
    }
}
var lines : Int = 0 //간선수
for index in 0..<arr.count{
    // 만약 추가된 간선수가 정점수 -1이면 끝
    if lines == N-1{
        break
    }
    if(find_parent(parent: &parent, x: arr[index][0]) != find_parent(parent: &parent, x: arr[index][1])){
        howmuch += arr[index][2]
        last = arr[index][2]
        union(parent: &parent, a: arr[index][0], b:   arr[index][1])
        lines+=1
    }
}
print(howmuch - last)

진짜찐짜 최종 sort보다 sort by 가 시간복잡도가 더 작다 해서 사용을 하였고  불필요한 2차배열도 안만들고... chat gpt도 모른다.

고로 나도 못한ㄷ.....