[Swift] BOJ 23034 조별과제 멈춰! (실패: 시간초과)

BOJ 23034 조별과제 멈춰!

 

 

시간초과로 지속적으로 실패해서 기록

 

도전과 실패,

 

 

그냥 쉽게 크루스칼 사용해서 풀면 되겠다 싶었는데, 시간 초과를 해결할 수 없었음.

 

Swift 언어로 통과한 사람이 아무도 없는걸 보면은 안되는건가 싶은데, 제출자는 풀었을거니까 천천히 다시 살펴보자

주어진 데이터 크기와 알고리즘을 고려해 보았을 때, 해결할 방법이 분명히 있을탠데 모르겠다.

 

시도한 방법 

1. FileIO 사용해서 데이터 빨리 입력 받기 (https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88)

2. cost의 범위를 Double로 바꾸기 (Int형 오버플로 날 수도 있어서)

3. questions tuple -> Array로 변경

 

- 내 코드에서 내가 생각하는 해결 방법.

크루스칼 알고리즘 후에 팀장들 간의 가중치를 알아서 그 값을 빼야 하는데, 여기서 서칭이 들어갈 때 시간 복잡도를 줄여야 할듯.

 

문제 풀이 알고리즘

알고리즘 설명

 

샘플 코드

// https://www.acmicpc.net/problem/23034
import Foundation

// MARK: - 실패한 문제 (시간초과)
struct b23034 {
    static func run() {
        
        
        let input = readLine()!.split(separator: " ").map { Int($0)! }
        
        var graph = [[Int]]()
        for _ in 0..<input[1] {
            graph.append(readLine()!.split(separator: " ").map { Int($0)! })
        }
        
        let questionCount = Int(readLine()!)!
        var questions = [(Int, Int)]()
        for _ in 0..<questionCount {
            let info = readLine()!.split(separator: " ").map { Int($0)! }
            questions.append((info[0], info[1]))
        }
        
        //        print(graph)
        //        print(questions)
        
        // N명의 학생만큼 부모 테이블 세팅
        var parent = Array(0...input[0])
        graph.sort { $0[2] < $1[2] }
        
        var result = 0
        graph.forEach {
            let a = $0[0]
            let b = $0[1]
            let cost = $0[2]
            
            // 사이클이 없다면
            if find(index: a) != find(index: b) {
                result += cost
                union(a: a, b: b)
            }
        }
        
        questions.forEach { question in
            var cost = 0
            
            for item in graph {
                if item[0] == question.0 && item[1] == question.1 {
                    cost = item[2]
                    break
                }
            }
            print(result - cost)
        }
        
        
        
        func find(index: Int) -> Int {
            if parent[index] == index {
                return index
            } else {
                parent[index] = find(index: parent[index])
                return parent[index]
            }
        }
        
        func union(a: Int, b: Int) {
            let num1 = find(index: a)
            let num2 = find(index: b)
            
            if num1 < num2 {
                parent[num2] = num1
            } else {
                parent[num1] = num2
            }
        }
    }
}