[백준/BOJ] 1325번: 효율적인 해킹

문제

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

1325번: 효율적인 해킹

해설

처음에는 플로이드 와샬 알고리즘을 통해 시도해보았지만, 시간 초과가 발생했다.

다음으로 dfs를 통해 문제를 해결할 수 있었다.

 

dfs를 수행할 때, 컴퓨터 사이에 신뢰를 하는지 저장할 ArrayList 자료형을 가진 배열과 방문 여부를 체크할 Boolean 배열, 해킹 가능한 컴퓨터의 수를 저장할 Int 배열을 선언하였다.

 

우선 (a, b)를 입력받으며 신뢰관계를 graph에 저장해준다.

-> graph[a].add(b)

 

이 과정이 끝났다면 각 컴퓨터마다 dfs 알고리즘을 수행시켜 해킹할 수 있는 컴퓨터의 수를 세면 된다.

dfs의 동작 방식은 코드를 보자.

코드

private lateinit var graph: Array<ArrayList<Int>>
private lateinit var visited: BooleanArray
private lateinit var hacking: IntArray
private var max = 0

fun main() = with(System.`in`.bufferedReader()){
    val (computerCnt, trustCnt) = readLine().split(" ").map { it.toInt() }

    graph = Array(computerCnt + 1) { ArrayList() }
    hacking = IntArray(computerCnt + 1)

    repeat(trustCnt) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        graph[a].add(b)
    }

    for(i in 1 .. computerCnt) {
        visited = BooleanArray(computerCnt + 1)
        visited[i] = true
        dfs(i)
    }

    for(i in 1 .. computerCnt) {
        if(hacking[i] == max) print("$i ")
    }
}

private fun dfs(n: Int) {
    hacking[n]++
    max = maxOf(max, hacking[n])

    for(i in graph[n].indices) {
        val nextComputer = graph[n][i]
        if(!visited[nextComputer]) {
            visited[nextComputer] = true
            dfs(nextComputer)
        }
    }
}