백준 1005번 ACM Craft - 스위프트(Swift) 시간초과 해결 못함

 단순한 위상 정렬 문제였는데 TLEㅠㅠ 입력이 느려서 그런 것 같다. 검색해보니 이 문제를 swift로 푼 사람들 중에 readLine() 대신 FileIO를 사용해서 AC를 받았다는 글이 몇 개 있었다. 결국 또 C++로 다시 제출했다.

 아래는 각각 시간초과 받은 Swift코드와 같은 로직인데 AC 받은 C++ 코드.

---

 

import Foundation

var N = 0, K = 0
var indegree = [Int]()
var buildCost = [Int]()
var totalCost = [Int]()
var edges = [[Int]]()

struct Queue {
    var queue = [Int]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func insert(_ n: Int) {
        queue.append(n)
    }
    
    mutating func popFront() -> Int {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func topologySort(target: Int) -> Int {
    totalCost = buildCost
    
    for start in 1...N {            // 초기 진입차수 계산
        for end in 1...N {
            if edges[start][end] == 1 { indegree[end] += 1 }
        }
    }
    
    var queue = Queue()
    for i in 1...N {
        if indegree[i] == 0 { queue.insert(i) }
    }
    
    while !queue.isEmpty {
        let current = queue.popFront()
     
        if current == target { return totalCost[current] }
        
        for end in 1...N {
            guard edges[current][end] == 1 else { continue }
        
            totalCost[end] = max(totalCost[end], totalCost[current] + buildCost[end])
            indegree[end] -= 1
            if indegree[end] == 0 { queue.insert(end) }     // 건설 완료
        }
    }
    
    return 0
}

func initTestcase() {
    indegree = Array(repeating: 0, count: 1001)
    edges = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)
}

func solution() {
    var resultString = ""
    var T = Int(readLine()!)!
    
    while T > 0 {
        initTestcase()
        
        var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        N = input[0]
        K = input[1]
        
        buildCost = [0] + readLine()!.split(separator: " ").map{ Int(String($0))! }
        
        for _ in 0..<K {
            input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let start = input[0]
            let end = input[1]
            
            edges[start][end] = 1
        }
        
        let W = Int(readLine()!)!
        
        resultString.write("\(topologySort(target: W))\n")
        
        T -= 1
    }
    
    print(resultString)
}

solution()

---

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int N, K;
int indegree[1001], buildCost[1001], totalCost[1001];
int edges[1001][1001];

int topologySort(int target) {
    for (int s = 1; s <= N; s++) {
        for (int e = 1; e <= N; e++) {
            if (edges[s][e] == 1) indegree[e]++;
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        totalCost[i] = buildCost[i];
        if (indegree[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        
        if (current == target) return totalCost[current];
        
        for (int end = 1; end <= N; end++) {
            if (edges[current][end] == 1) {
                totalCost[end] = max(totalCost[end], totalCost[current] + buildCost[end]);
                indegree[end]--;
                if (indegree[end] == 0) q.push(end);
            }
        }
    }
    
    return 0;
}

void initTestcase() {
    memset(indegree, 0, 1001 * sizeof(int));
    memset(totalCost, 0, 1001 * sizeof(int));
    memset(edges, 0, 1001 * 1001 * sizeof(int));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T) {
        initTestcase();
        
        cin >> N >> K;
        
        for (int i=1; i<=N; i++) {
            int x;
            cin >> x;
            buildCost[i] = x;
        }
        
        for (int i=0; i<K; i++) {
            int s, e;
            cin >> s >> e;
            edges[s][e] = 1;
        }
        
        int W;
        cin >> W;
        cout << topologySort(W) << "\n";
        
        T--;
    }

    return 0;
}