[백준 1325번] [Kotlin] 효율적인 해킹

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

1325번: 효율적인 해킹

 

난이도 :  실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

DFS/BFS를 응용해 풀 수 있을 것 같습니다.

다만 주의할 점은, 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터들을 순차적으로 출력해야 하므로,

모든 컴퓨터에 대해 탐색을 진행해야 합니다.

 

 

 

소스코드

import java.lang.StringBuilder
import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val connection = Array(n + 1) { ArrayList<Int>() }
    val result = Array(n + 1) { 0 }

    repeat(m) {
        val st = StringTokenizer(readLine())
        connection[st.nextToken().toInt()].add(st.nextToken().toInt())
    }

    for (i in 1..n) {
        val visited = Array(n + 1) { false }
        visited[i] = true

        val q = LinkedList<Int>() as Queue<Int>
        q.offer(i)

        while (q.isNotEmpty()) {
            val target = q.poll()

            connection[target].forEach { nextNode ->
                if (!visited[nextNode]) {
                    visited[nextNode] = true
                    q.offer(nextNode)
                    result[nextNode]++
                }
            }
        }
    }

    val max = result.maxOrNull()!!
    val sb = StringBuilder()
    
    result.forEachIndexed { index, value ->
        if(value == max) sb.append(index).append(" ")
    }
    println(sb)
}

 

result는 각 컴퓨터가 해킹할 수 있는 컴퓨터 개수입니다.

BFS를 한 번 진행할 때 마다 하나씩 증가시키고,

모든 노드(컴퓨터)에 대해 탐색을 진행합니다.

 

최종적으로, result 내 가장 큰 숫자와 같은 숫자의 index 들을 출력합니다.

 

 

후기

각 컴퓨터가 해킹할 수 있는 컴퓨터 개수를 어떻게 구하지... 분리 집합을 사용해야 하나? 생각하다가,

혹시 하는 마음에 모든 컴퓨터에 대해 탐색을 진행했더니 풀렸습니다.

때로는 쉽게 생각해야 하나 봅니다...