[프로그래머스] 전력망을 둘로 나누기 in Kotlin

📜 문제

문제 링크

💡 나의 풀이

1. input으로 주어진 wires를 순회하면서 인접리스트로 트리를 구성한다.
2. wires를 순회하면서 해당 wire를 제거했을 때 나뉜 두 전력망이 가지고 있는 송전탑의 개수 차이를 구하고, answer보다 작으면 answer를 갱신한다.
    -> 이때 전력망이 가지고 있는 송전탑의 개수를 bfs로 구했다.

⌨️ 코드

import kotlin.math.*

class Solution {
    
    private var answer: Int = 100

    fun solution(n: Int, wires: Array<IntArray>): Int {
        val tree = Array(n + 1) {
            mutableListOf<Int>()
        }

        // 1. 트리 구성
        wires.forEach { wire ->
            val v1 = wire[0]
            val v2 = wire[1]

            tree[v1].add(v2)
            tree[v2].add(v1)
        }

        // 2. wires를 순회하면서 해당 wire를 제거했을 때 나뉜 두 전력망이 가지고 있는 송전탑 개수의 차이를 구함
        wires.forEach { wire ->
            val network1 = towerCount(wire[0], wire[1], tree, BooleanArray(n + 1))
            val network2 = towerCount(wire[1], wire[0], tree, BooleanArray(n + 1))

            answer = answer.coerceAtMost((network1 - network2).absoluteValue)
        }

        return answer
    }

	// bfs로 v1을 포함하는 전력망에 있는 송전탑의 개수를 구함
    fun towerCount(v1: Int, v2: Int, tree: Array<MutableList<Int>>, visited: BooleanArray): Int {
        var count = 1
        val queue = ArrayDeque<Int>()
        visited[v1] = true
        queue.add(v1)

        while (queue.isNotEmpty()) {
            val current = queue.removeFirst()

            tree[current].forEach { next ->
                if (!visited[next] && next != v2) {
                    count++
                    visited[next] = true
                    queue.add(next)
                }
            }
        }

        return count
    }
}

😄 느낀 점

모든 간선들에 대해서 한번씩 빼면서 bfs를 수행해야하기 때문에 대략 O(N^2)의 시간복잡도지만, N의 범위가 최대 100이기 때문에 시간적으로 문제가 되지 않을 것이라고 판단해서 풀었다! 완전탐색 문제여서 출제 의도도 이게 맞는 거 같은데 뭔~~~가 O(N^2)면 넘 찝찝하당,,ㅎㅅㅎ,,,,