(BOJ) 1506 경찰서

1506 경찰서

• 분류 : 강한 연결 요소

문제

종욱이가 살고있는 나라에는 도시가 N개 있고, 도시의 일부는 일방 통행 도로로 연결되어 있다.

종욱이가 살고있는 나라의 대통령 욱종이는 범죄와 싸우기 위해서 일부 도시에 경찰서를 세우려고 한다.

도시 i에 경찰서를 세우는 비용은 cost[i] 이다.

도시 i에 세운 경찰서가 도시 j를 통제할 수 있으려면, i에서 j로 갔다가, 다시 돌아오는 경로가 존재해야 한다.

도로가 연결되어 있는 상태와 각 도시에 경찰서를 지을 때 필요한 비용이 주어졌을 때, 모든 도시를 통제하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 각 도시에 경찰서를 세우는데 드는 비용이 주어진다. 셋째 줄부터 도로가 연결되어 있는 상태가 한 줄에 한 줄에 하나씩 주어진다. i번째 줄의 j번째 문자가 0인 경우에는 도시 i에서 도시 j로 갈 수 없는 것이고, 1인 경우에는 갈 수 있는 것이다.

경찰서를 세우는 비용은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 도시를 통제하는데 필요한 최소 비용을 출력한다.

예제 입력 1

5
1 2 3 4 5
00011
10000
00010
00100
01000

예제 출력 1

4

Solution

Exapnder

package boj

import java.util.*
import kotlin.math.min

private const val MAX = 101

private var N: Int = 0
private var cost = IntArray(MAX) { 0 }
private var graph = Array(MAX) {
    IntArray(MAX) { 0 }
}

fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
    for (i in 0 until N) {
        cost[i] = nextInt()
    }
    for (i in 0 until N) {
        var str = next()
        for (j in 0 until N) {
            graph[i][j] = str[j].toInt() - 48
        }
    }
}

private fun solve() {
    // Step 1 : 모든 가능 정점을 잇는다.
    for (k in 0 until N) {
        for (i in 0 until N) {
            for (j in 0 until  N) {
                if (graph[i][k] == 1 && graph[k][j] == 1) {
                    graph[i][j] = 1
                }
            }
        }
    }
    // Step 2 : 정점을 순회면서, 정점에 cost가 0이 아닌 경우 (=즉 경찰서를 지어야 하는 경우) 최소 비용을 계산하여 넣는다. 
    var result: Int = 0
    for (i in 0 until N) {
        if (cost[i] == 0) {
            continue
        }
        var c = cost[i]
        cost[i] = 0
        for (j in 0 until N) {
            if (graph[i][j] == 1 && graph[j][i] == 1 && cost[j] > 0) {
                c = min(c, cost[j])
                cost[j] = 0
            }
        }
        result += c
    }
    println("$result")
}

Point of Thinking

• 모든 정점이 이어졌을 때, 최소 비용을 구한다.
• 실제 알고리즘에서 edge에 부여된 weight는 존재하지않지만, 경찰서를 짓기 위한 cost를 대신 검증하면 된다.
  • 즉 모든 정점을 순회할 수 있을 때, 모든 cost가 0 으로 초기화되는 경우 경찰서를 다 지은 것이다.
• 간선간 비용이 존재하지 않고, 갈 수 있냐 없냐만 판단하면 되므로 Floyd Algorithm으로 경로를 탐색하면 된다.
• Step 1. 모든 가능 정점을 잇는다.
• Step 2. 정점을 순회면서, 정점에 cost가 0이 아닌 경우 (=즉 경찰서를 지어야 하는 경우) 최소 비용을 계산하여 넣는다.
  • Floyd 특성상 모든 정점을 순회만 하면 최적해가 나온다.