글 읽기 - kruskal 알고리즘 구현문제에서, 틀린 부분을 못찾겠습니다. (swift)

inseu99 2년 전 0

1197번 문제를 swift를 통해 kruskal 알고리즘으로 풀어봤습니다.

나름 문제없는 코드 같은데, 틀렸다고 나옵니다.

예제를 만들어서 풀어보고 print 해가며 잘못된 곳을 찾아보려 해도 찾아지지가 않네요.

혹시 반례나, 잘못된 부분이 있다면 찾아주시면 정말 감사하겠습니다.

let input = readLine()!.split(separator: " ").map { Int($0)! }
let v = input[0]
let e = input[1]
var graph = [[Int]]()

for _ in 0..<e {
    graph.append(readLine()!.split(separator: " ").map { Int($0)! })
}

print(kruskal(input: graph))

func kruskal(input: [[Int]]) -> Int {
    var graph = input.sorted { $0[2] > $1[2] }  // weight의 내림차 순으로 정렬 (removeLast를 위해)
    var mst = [[Int]]()                         // 최소신장트리가 들어갈 곳
    var parents = [Int](0...v)                  // cycle 확인을 위한 배열
    
    while mst.count < v-1 {                    // 간선의 개수는 (정점의 개수-1) 개 이므로 v-1 회 반복
        addMst(input: graph.removeLast())      // weight의 내림차순 정렬된 마지막값 즉, 가장 작은 weight 부터 추가
    }
    
    func addMst(input: [Int]) {                 // cycle 이 생기지 않으면 해당 간선을 mst에 추가
        if !isCycle(input: input) {
            mst.append(input)
            updateParents(input: input)
        }
    }
    
    func isCycle(input: [Int]) -> Bool {        // cycle 확인, 시작점과 도착점의 parents 가 같다면 cycle임.
        return getParents(input: input[0]) == getParents(input: input[1])
    }
    
    func getParents(input: Int) -> Int {
        if parents[input] != input {
            parents[input] = getParents(input: parents[input])
        }
        return parents[input]
    }
    
    func updateParents(input: [Int]) {          // 더 작은 index로 parents를 설정.
        if getParents(input: input[0]) > getParents(input: input[1]) {
            parents[input[0]] = parents[input[1]]
        } else {
            parents[input[1]] = parents[input[0]]
        }
    }
    
    return mst.compactMap { $0[2] }.reduce(0, { $0 + $1 })  // mst의 weight를 모두 합친 값을 반환.
}

inseu99 2년 전 0

해결했습니다!. update 시에 update 가 안되는 경우들이 있었네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

kruskal 알고리즘 구현문제에서, 틀린 부분을 못찾겠습니다. (swift)

inseu99 2년 전 0

inseu99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말