[백준 11724번] 연결 요소의 개수 - Kotlin

[백준 11724번] 연결 요소의 개수 - Kotlin

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

---

문제

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

---

입력

• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.
  • (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.
  • (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

---

출력

• 첫째 줄에 연결 요소의 개수를 출력한다.

---

풀이

private class Solution11724 {

    fun solution(graph: Array<Node>): Int {
        var result = 0
        val visited = BooleanArray(graph.size)

        for (i in 1 until graph.size) {
            if (dfs(i, graph, visited)) {
                result += 1
            }
        }

        return result
    }

    private fun dfs(
        start: Int,
        graph: Array<Node>,
        visited: BooleanArray
    ): Boolean {
        if (visited[start]) {
            return false
        }

        val node = graph[start]
        visited[start] = true

        for (subNode in node.sub) {
            if (!visited[subNode]) {
                dfs(subNode, graph, visited)
            }
        }

        return true
    }

    data class Node(
        val num: Int,
        val sub: MutableList<Int> = mutableListOf()
    )
}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (n, m) = br.readLine().split(" ").map(String::toInt)
    val graph = Array(n + 1) { Solution11724.Node(it) }

    repeat(m) {
        val (a, b) = br.readLine().split(" ").map(String::toInt)
        graph[a].sub.add(b)
        graph[b].sub.add(a)
    }

    bw.append("${Solution11724().solution(graph)}\n")
    bw.flush()

    br.close()
    bw.close()
}