[백준 1005] ACM craft (Swift)

https://www.acmicpc.net/problem/1005

 

위상정렬, DP, DFS (?)

건물들의 건설시간과 건설 순서가 주어진다 (건설 순서 : a, b (a지은 후 b를 지을 수 있음))

이때 W번 건물이 지어질 수 있는 가장 짧은 시간 구하는 문제

위의 사진의 경우 4번 건물을 2와 3이 모두 지어진 후인 110초 후에 지어지기 시작해서 120초가 걸려야 지어짐

 

접근방법

part 1. 재귀 DFS + DP로 풀어보려고 시도

얼마전에 그 강 순서 구하는 것 처럼 구해야할 노드에서 시작해서 역으로 구해보려고 했는데 시간초과났음

 

part 2. 위상정렬

선행하는 노드들이 먼저 수행되어야 내가 수행될 수 있다 -> 이전에 줄세우기 문제와 유사함

위상 정렬 사용해서 풀이해야 하는 문제라서 어떻게 할지 고민하다가 줄세우기 문제를 참고해서

건물 순서 입력 받으면서, 나를 세우기 위해 먼저 세워야 하는 건물들의 수를 cnt 배열에 저장한다.

time 배열에 나를 건설하는 데 걸리는 시간이 저장되도록 했다.

cnt 배열의 값이 0인 경우를 큐에 담고

큐에서 하나씩 빼면서, time 배열을 갱신해간다.

갱신 방식 : 내가 지어진 후에 지어질 수 있는 건물의 cnt를 하나씩 빼주고, 그 건물의 time 값을 (내가 지어지고 이 건물을 지었을 때와 현재 그 건물의 time값)을 비교해서 큰값으로 갱신해준다. (순서상으로 나 이전의 건물들이 모두 지어져야 나를 지을 수 있기 때문에 상한값에 맞추어야 한다)

끝

 

오답노트

처음엔 케이스마다 출력하는 식으로 했는데 5%쯤에서 틀렸습니다 떴음

그래서 배열로 케이스별 정답 저장해서 마지막에 한꺼번에 출력했더니 맞았음

교훈: 5%에서 틀렸다고 떠도 출력형식의 문제일수있다.

 

소스코드

import Foundation

func solution() {
    var result:[Int] = []
    
    // input
    let T:Int = Int(readLine()!)!
    for _ in 0..<T {
        // case start
        
        let NK:[Int] = (readLine()?.split(separator:" ").map { Int($0)! })!
        let N = NK[0]
        let K = NK[1]
        
        var D:[Int] = [0]
        D += (readLine()?.split(separator:" ").map { Int($0)! })!
        
        var adj:[[Int]] = [[Int]](repeating: [], count: N+1)
        var cnt:[Int] = [Int](repeating: 0, count: N+1)
        
        for _ in 0..<K {
            let xy:[Int] = (readLine()?.split(separator:" ").map { Int($0)! })!
            adj[xy[0]].append(xy[1])
            cnt[xy[1]] += 1
        }
        
        let W:Int = Int(readLine()!)!
        var time:[Int] = D
        
        // 위상정렬 큐 초기화
        var q:[Int] = []
        for i in 1...N {
            if cnt[i] == 0 {
                q.append(i)
            }
        }
        
        while !q.isEmpty {
            let now = q.removeFirst()
            for bd in adj[now] {
                cnt[bd] -= 1
                time[bd] = max(time[bd], time[now]+D[bd])
                if cnt[bd] == 0 {
                    q.append(bd)
                }
            }
        }
        
        result.append(time[W])
        // case end
    }
    result.forEach{ print($0) }
}

solution()