[BOJ] 18250 철도 여행 - P5

TaeGN·2024년 8월 28일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

39/114

문제풀이

연결되어 있는 지점들에서 inDegree가 홀수인 개수를 구하고 그것을 2로 나눈 값이 모든 경로를 지나는데 필요한 횟수이다. (inDegree가 홀수인 개수가 0이고, inDegree > 0 이면 필요한 횟수는 1이다.)

주의사항

소요시간

1시간

package 백준.Platinum.P5.p18250_철도여행

fun main() {
    val (N, M) = readln().split(" ").map(String::toInt)
    val inDegree = IntArray(N + 1)
    val roadLists = List(N + 1) { mutableListOf<Int>() }
    repeat(M) {
        val (A, B) = readln().split(" ").map(String::toInt)
        roadLists[A].add(B)
        roadLists[B].add(A)
        inDegree[A]++
        inDegree[B]++
    }
    val visited = BooleanArray(N + 1)
    fun dfs(from: Int): Int {
        visited[from] = true
        var oddCount = inDegree[from] % 2
        for (to in roadLists[from]) {
            if (visited[to]) continue
            oddCount += dfs(to)
        }
        return oddCount
    }

    var result = 0
    for (i in 1..N) {
        if (!visited[i] && inDegree[i] != 0) result += maxOf(1, dfs(i) / 2)
    }
    println(result)
}