[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
            }
        }
    }
}

 

 

누가 이 문제를 푼다면 댓글을 꼭 남겨주세여!