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

해당 문제는 DFS를 연습하기 좋은 문제이기에 작성해 보았습니다.

만약 이 글을 보시는 분이 DFS를 연습하신다면 해당 문제는 DFS의 기초를 다지기에는 매우 좋은 문제 입니다.

DFS(깊이 우선 탐색) 를 하며 연결된 노드들을 count 하기때문입니다.

해당 문제와 유사한 문제로는 프로그래머스의 네트워크 문제가 있기에 그 문제도 풀어보시면 좋을 것 같습니다.

네트워크 문제 작성 코드 링크 입니다.

https://want-kotlin-pro.tistory.com/92

[프로그래머스][Kotlin] 네트워크

 

하기는 11724번 연결 요소의 개수 문제 작성한 코드와 제출 결과 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

lateinit var visted : BooleanArray
var loadMap = mutableMapOf<Int,IntArray>()

fun main() {
    //val s = System.currentTimeMillis()
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt() // 노드의 개수
    val M = st.nextToken().toInt() // 에지의 개수
    repeat(M){
        st = StringTokenizer(br.readLine())
        val key = st.nextToken().toInt()
        val value = st.nextToken().toInt()
        //양방향 노드라서 번가라 가며 2번 입력
        if(loadMap.containsKey(key)){
            loadMap[key] = loadMap[key]!! + intArrayOf(value)
        }else{
            loadMap[key] = intArrayOf(value)
        }
        if(loadMap.containsKey(value)){
            loadMap[value] = loadMap[value]!! + intArrayOf(key)
        }else{
            loadMap[value] = intArrayOf(key)
        }
    }

    visted = BooleanArray(N+1){true} // 방문 여부

    var result = 0

    for(i in 1 .. N){
        if(visted[i]){
            check(i)
            result++
        }
    }
    println(result)
}

fun check(viste: Int){
    visted[viste] = false
    loadMap[viste]?: return // Null 안정성
    
    for (i in loadMap[viste]!!){
        if(visted[i]) {
            check(i)
        }
    }
    
}