[Programmers] 전력망을 둘로 나누기

주어진 트리의 간선 하나를 끊어서 두개의 트리를 만드는데, 나눠진 두 트리의 노드 갯수를 최대한 비슷하게 만들었을 때, 두 트리의 노드 갯수 차이를 구하는 문제이다.

 

문제를 처음 봤을 때 hashmap이나 이차원 배열, 재귀 이 세가지 방법으로 풀 수 있을 것 같았다. 

처음에는 문제를 꼼꼼히 안 읽어서 입력값이 [부모,자식] 인 줄 알았다.

 

입력값이 이차원 배열 형태인데, 각 노드의 숫자는 부모/자식 관계와는 상관이 없었다.

또, 노드 번호가 연속된다는 보장이 없다.

 

따라서 hashmap이나 Dequeue를 이용한 풀이가 더 효율적일것이다. (하지만 다시짜기 귀찮아..서.. 그냥 제출했다)

 

아무튼, 입력값을 받아서 노드들을 만들어주고, 연결해서 트리를 만든다음 첫번째 노드를 시작으로 트리를 순회하면서 각 노드의 자식 노드들의 갯수를 구하고, 현재 노드와 부모 노드를 연결한 간선을 끊었을 때 두 트리의 노드 차를 최소가 되도록 갱신하면서 답을 구했다.

방향성이 없어서 부모/자식을 판단할 수 없기 때문에 각 노드를 방문할 때 마다 visit 처리를 해줬다.

class Splitting_the_power_grid_in_half {

    var answer = 0
    lateinit var arr: MutableList<Node>
    lateinit var visited: MutableList<Boolean>
    var size = 0
    fun solution(n: Int, wires: Array<IntArray>): Int {
        answer = n
        size = n
        arr = MutableList<Node>(101) { Node(it) }
        visited = MutableList<Boolean>(101) { false }

        for (nxt in wires) {
            arr[nxt[0]].child.add(arr[nxt[1]])
            arr[nxt[1]].child.add(arr[nxt[0]])
        }

        find(arr[wires[0][0]])

        return answer
    }

    fun find(current: Node): Int {
        if (visited[current.no]) return 0
        visited[current.no] = true
        var value = 1
        for (nxt in current.child) {
            value += find(nxt)
        }
        answer = min(abs(size - value * 2), answer)
        return value
    }

    data class Node(
            var no: Int,
            var child: MutableList<Node> = mutableListOf()
    )
}