폭발물 설치

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• SCC 문제를 응용한 문제로, 코사라주 알고리즘에서 역방향 그래프에 대해서 DFS를 한번 더 적용하는 것과 다르게 생각해야 함
• 결론적으로, SCC인 그래프들은 어떠한 정점을 터뜨려도 다 터지기 때문에 1개의 정점으로 봐도 무방함
• 따라서 SCC인 그래프들을 1개의 정점으로 보고, 나머지에 대해 가장 효율적이게 폭발물을 설치해야 하는데, 자세히 살펴보면
• 나에게 들어오는 간선이 없는 정점에 대해 터뜨리게 되면 가장 최소한의 다이너마이트를 사용하여 폭발물을 설치할 수 있음
• 이를 코사라주 알고리즘을 응용하여 빠져나오는 순서를 기록하고, 재귀함수(DFS)의 특성상 가장 나중에 빠져나온 정점이 나에게 들어오는 간선이 없는 간선이므로, 이번에는 역방향이 아닌 원래 정방향 그래프에 대해 가장 나중에 빠져나온 정점부터 DFS를 한번 더 적용함으로써 문제를 해결할 수 있음
• 따라서 O(V + E)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 폭발물 설치

//MARK: - Framework
import Foundation

//MARK: - Type
struct Graph {
    //MARK: - Property
    var edges: [Int]
    
    //MARK: - Init
    init() {
        self.edges = []
    }
}

//MARK: - Variable
var graph: [Graph] = []
var visited: [Bool] = []
var orders: [Int] = []
var orderCount: Int = 0

//MARK: - Function
func getOrderDFS(_ x: Int) -> Void {
    visited[x] = true
    
    for i in 0..<graph[x].edges.count {
        let y: Int = graph[x].edges[i]
        
        if !visited[y] {
            getOrderDFS(y)
        }
    }
    
    orders.append(x)
}

func graphDFS(_ x: Int) -> Void {
    visited[x] = true
    
    for i in 0..<graph[x].edges.count {
        let y: Int = graph[x].edges[i]
        
        if !visited[y] {
            graphDFS(y)
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    let N: Int = input.map { Int($0) }[0] ?? 0
    let M: Int = input.map { Int($0) }[1] ?? 0
    var dynamiteCount: Int = 0
    
    graph = Array(repeating: Graph(), count: N + 10)
    visited = Array(repeating: false, count: N + 10)
    
    for _ in 0..<M {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        let a: Int = inputData.map { Int($0) }[0] ?? 0
        let b: Int = inputData.map { Int($0) }[1] ?? 0
        
        graph[a].edges.append(b)
    }
    
    //MARK: - Process
    for i in stride(from: 1, through: N, by: 1) {
        if !visited[i] {
            getOrderDFS(i)
        }
    }
    
    visited = Array(repeating: false, count: N + 10)
    
    for i in stride(from: orders.count - 1, through: 0, by: -1) {
        if !visited[orders[i]] {
            graphDFS(orders[i])
            dynamiteCount += 1
        }
    }
    
    //MARK: - Output
    print(dynamiteCount)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.