[BOJ] 1506 경찰서 - P5

문제풀이

1. 타잔 알고리즘을 사용하여 SCC 구하기
2. 각각의 SCC에서 최소 비용을 구해서 더하기

---

주의사항

---

소요시간

15분

---

package 백준.Platinum.P5.p1506_경찰서

import java.util.StringTokenizer
import kotlin.math.min

const val EMPTY = 0

fun main() {
    val N = readln().toInt()
    val st = StringTokenizer(readln())
    val costArr = IntArray(N)
    repeat(N) { idx -> costArr[idx] = st.nextToken().toInt() }
    val matrix = Array(N) { BooleanArray(N) }
    repeat(N) { r ->
        val input = readln()
        repeat(N) { c -> matrix[r][c] = input[c] == '1' }
    }

    val finishArr = BooleanArray(N)
    val parentArr = IntArray(N)
    val stack = ArrayDeque<Int>()
    var result = 0
    var id = 0
    fun dfs(from: Int): Int {
        parentArr[from] = ++id
        stack.addFirst(from)
        var parent = parentArr[from]
        for (to in 0 until N) {
            if (matrix[from][to]) {
                if (parentArr[to] == EMPTY) parent = min(parent, dfs(to))
                else if (!finishArr[to]) parent = min(parent, parentArr[to])
            }
        }

        if (parent == parentArr[from]) {
            var minCost = Int.MAX_VALUE
            while (true) {
                val idx = stack.removeFirst()
                minCost = min(minCost, costArr[idx])
                finishArr[idx] = true
                if (idx == from) break
            }
            result += minCost
        }

        return parent
    }

    for (i in 0 until N) {
        if (!finishArr[i]) dfs(i)
    }
    println(result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p1506_%EA%B2%BD%EC%B0%B0%EC%84%9C/p1506_%EA%B2%BD%EC%B0%B0%EC%84%9C.kt

---

문제링크

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