백준 - 임계경로 (1948)

struct Node {
    let target: Int
    let value: Int
}

let n = Int(readLine()!)!
let m = Int(readLine()!)!
var graph: [[Node]] = Array(repeating: [], count: n+1)
var reverseGraph: [[Node]] = Array(repeating: [], count: n+1)
var indegree = Array(repeating: 0, count: n+1)
var result = Array(repeating: 0, count: n+1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph[input[0]].append(Node(target: input[1], value: input[2]))
    reverseGraph[input[1]].append(Node(target: input[0], value: input[2]))
    indegree[input[1]] += 1
}

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (start, end) = (input[0], input[1])

// 위상정렬로 임계경로 값 업데이트
var stack = [start]

while !stack.isEmpty {
    let now = stack.removeLast()
    for next in graph[now] {
        indegree[next.target] -= 1
        result[next.target] = max(result[next.target], result[now] + next.value)
        if indegree[next.target] == 0 {
            stack.append(next.target)
        }
    }
}

// 쉬지 않고 달려야 하는 도로 수 구하기
var resultCount = 0
var visited = Array(repeating: false, count: n+1)
stack = [end]
visited[end] = true

while !stack.isEmpty {
    let now = stack.removeLast()
    for next in reverseGraph[now] {
        if result[next.target] + next.value == result[now] {
            resultCount += 1
            if !visited[next.target] {
                stack.append(next.target)
                visited[next.target] = true
            }
        }
    }
}

print(result[end])
print(resultCount)

1. 임계경로는 위상정렬 알고리즘을 사용하여 구할 수 있다.
   1. 출발 도시가 정해져 있기 때문에 출발 도시에서부터 시작해서 위상정렬을 실행한다.
   2. 이때 result (각 도시의 최대 임계경로를 저장하는 배열)의 값은 max(현재 도시의 최대 임계경로, 이전 도시의 최대 임계경로 + 현재 도로를 지나는데 걸리는 시간 으로 설정한다.
2. 쉬지 않고 달려야 하는 도로의 수는 역방향 인접 리스트를 사용하여 구할 수 있다.
   1. 앞의 과정과 반대로 도착 도시에서부터 시작해서 역방향 인접 리스트를 사용하여 위상정렬을 실행한다.
   2. 이때 현재 도시의 임계경로 값 + 현재 도로를 지나는데 걸리는 시간 == 이전 도시의 임계경로 값 이라면 도로의 수를 1 증가시킨다. 그리고 현재 도시를 방문하지 않았다면 스택에 삽입한 후 방문 표시를 해준다. (중복으로 계산되는 것을 방지하기 위함)
3. 최종적으로 계산된 도착 도시의 임계경로와 도로의 수를 출력한다.