만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 4196 도미노

23 Jun 2021

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

도미노 블럭 하나가 정점 하나에 해당한다고 했을 때 모든 도미노를 쓰러뜨리기 위해 넘어뜨려야 하는 최소 횟수를 구하는 문제이다. 도미노 블록간에 위상관계를 세우고 위상정렬을 하면 좋겠다는 생각이 들 것이다.

하지만 주의할 것은 앞에서와는 다르게 사이클이 존재한다는 것이다. 사이클이 있는 그래프에서는 위상정렬을 할 수 없기 때문에 약간의 변화가 필요하다. SCC를 생각해보면 SCC 집합들 간에는 사이클이 존재할 수 없다고 설명했었다. 따라서 SCC집합으로 그래프를 바꾸고 SCC 집합간에 위상정렬을 실행하면 간단히 해결할 수 있다.

func dfsB(n: Int, scc: Int) {
    SCC[n] = scc
    for e in edgeB[n] {
        if SCC[e] == 0 {
            dfsB(n: e, scc: scc)
        }
        else if SCC[e] != SCC[n] {
            indegree[scc] += 1
        }
    }
}

여기서는 코사라주로 구현을 했는데 그 중 dfsBack Function의 마지막 else if 구문을 보자. 코사라주에서 SCC 집합을 만들면 위상 관계가 있다면 위상 관계상 먼저 와야하는 SCC 집합이 먼저 만들어진다고 했었다. 따라서 본인과 SCC집합이 다른 정점을 만나게된다면 이는 본인의 SCC집합을 향하는 edge가 있다는 뜻이고 indegree값이 증가해야 함을 의미한다. 최종적으로는 indegree값이 0인 SCC집합들의 갯수를 새서 출력해주면 된다.

var edgeF:[[Int]] = []
var edgeB:[[Int]] = []
var check:[Bool] = []
var SCC:[Int] = []
var indegree:[Int] = []
var ft:[Int] = []
var index = 1

func dfsF(n: Int) {
    check[n] = true
    for e in edgeF[n] {
        if !check[e] {
            dfsF(n: e)
        }
    }
    ft[index] = n
    index += 1
}

func dfsB(n: Int, scc: Int) {
    SCC[n] = scc
    for e in edgeB[n] {
        if SCC[e] == 0 {
            dfsB(n: e, scc: scc)
        }
        else if SCC[e] != SCC[n] {
            indegree[scc] += 1
        }
    }
}

let t = Int(readLine()!)!
for _ in 0..<t {
    let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
    let n = nm[0], m = nm[1]
    var scc = 0, result = 0
    edgeF = Array(repeating: [], count: n+1)
    edgeB = Array(repeating: [], count: n+1)
    check = Array(repeating: false, count: n+1)
    SCC = Array(repeating: 0, count: n+1)
    indegree = Array(repeating: 0, count: n+1)
    ft = Array(repeating: 0, count: n+1)
    index = 1
    for _ in 0..<m {
        let line = readLine()!.split(separator: " ").map{Int(String($0))!}
        let N1 = line[0], N2 = line[1]
        edgeF[N1].append(N2)
        edgeB[N2].append(N1)
    }
    
    for i in 1...n {
        if !check[i] {
            dfsF(n: i)
        }
    }
    for i in 1...n {
        let node = ft[n+1-i]
        if SCC[node] == 0 {
            scc += 1
            dfsB(n: node, scc: scc)
        }
    }

    for i in 1...scc {
        if indegree[i] == 0 {
            result += 1
        }
    }
    print(result)
}

Related posts