<프로그래머스> 전력망을 둘로 나누기(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84%20%EB%91%98%EB%A1%9C%20%EB%82%98%EB%88%84%EA%B8%B0

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=kotlin

 

오랜만에 보는 트리(그래프) 문제였다.

그런데 상단 카테고리에 완전탐색을 보고는 마음이 좀 편해졌다.

그렇게 어렵지는 않겠구나

처음 알고리즘만 잘 잡으면 해결되겠다는 생각이 들었다.

 

난 인접 행렬로 그래프를 구성했다.

크기 제한이 최대 100이었기 때문이다.

그 후 각각의 노드에 양방향으로 에지를 추가했다.

그 다음은 간단하게 한 에지를 없애고 bfs돌리고 에지 다시 붙여주고를 반복했다.

bfs 내에서는 노드와 연결된 다른 노드를 확인하고 이어져있는 개수를 확인하고 둘로 나뉜 전력망 그룹의 송전탑 개수의 차이를 구해서 반환했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import kotlin.math.abs

class Solution {
    // 전력망
    private lateinit var network: Array<Array<Boolean>>
    // 방문여부
    private lateinit var visited: Array<Boolean>
    fun solution(n: Int, wires: Array<IntArray>): Int {
        var answer: Int = 100
        network = Array(n + 1) { Array(n + 1) { false } }

        // 에지 설정
        for (wire in wires) {
            network[wire[0]][wire[1]] = true
            network[wire[1]][wire[0]] = true
        }

        for (wire in wires) {
            visited = Array(n + 1) { false }

            network[wire[0]][wire[1]] = false
            network[wire[1]][wire[0]] = false

            answer = minOf(answer, diffTower(n))

            network[wire[0]][wire[1]] = true
            network[wire[1]][wire[0]] = true
        }
        
        return answer
    }
    
    // bfs
    private fun diffTower(n: Int): Int {
        var sum = 0
        val q = ArrayDeque<Int>()
        q.add(1)
        visited[1] = true
        sum++

        while (!q.isEmpty()) {
            val curNum = q.removeFirst()

            for (i in 1 until network.size) {
                if (network[curNum][i] && !visited[i]) {
                    q.add(i)
                    visited[i] = true
                    sum++
                }
            }
        }
        // 송전탑 개수의 차이(절댓값) 반환
        return abs(n - sum * 2)
    }
}