문제 링크

문제 간단 해석

현재 노드를 기준으로, 전체 노드 갯수에서 현재 노드 및 하위 노드들의 갯수를 뺀 값의 차가 최소가 되게끔 하는 문제.

Java

재귀를 이용하여 풀었다. 모든 노드에 진입하며, 전력망을 끊었을 때의 최솟값을 계산한다.

풀이 코드

import java.util.*;

class Solution {
    private Map<Integer, List<Integer>> tree = new HashMap<>();
    private int length;
    private int answer;

    public int count(int parent, int now) {
        int cnt = 1;

        for (int child: tree.get(now)) {
            if (child == parent)
                continue;

            cnt += count(now, child);
        }

        if (answer > Math.abs(2 * cnt - length))
            answer = Math.abs(2 * cnt - length);

        return cnt;
    }    

    public int solution(int n, int[][] wires) {
        this.length = wires.length + 1;
        this.answer = wires.length + 1;

        for (int[] wire: wires) {
            for (int i = 0; i < 2; i++) {
                if (!tree.containsKey(wire[i]))
                    tree.put(wire[i], new ArrayList<>());

                tree.get(wire[i]).add(wire[1 - i]);
            }
        }

        count(0, 1);

        return answer;
    }
}

해석

for (int[] wire: wires) {
    for (int i = 0; i < 2; i++) {
        if (!tree.containsKey(wire[i]))
            tree.put(wire[i], new ArrayList<>());

        tree.get(wire[i]).add(wire[1 - i]);
    }
}

count(0, 1);

return answer;

wires의 연결을 tree 형태로 구성하게끔 한다.
tree는 본인 노드 번호를 key로, 본인 노드와 연결된 노드들을 list로 갖는다.

그 후 count 함수를 돌려 내 노드 및 하위 노드들의 전체 갯수를 구한다.

public int count(int parent, int now) {
    int cnt = 1;

    for (int child: tree.get(now)) {
        if (child == parent)
            continue;

        cnt += count(now, child);
    }

    if (answer > Math.abs(2 * cnt - length))
        answer = Math.abs(2 * cnt - length);

    return cnt;
}    

현재 노드와 연결된 노드들을 모두 확인한다. 이 때, 가져온 연결 노드가 부모 노드라면 건너뛴다.
내 하위 노드들의 전체 갯수를 알아야 하기에, 재귀를 통해 구할 수 있도록 한다.

만약 현재 노드에서 부모 노드와의 연결점을 끊는다면, 두 전력망의 송전탑 갯수는 cnt와 전체 노드 갯수 - cnt일 것이다. 따라서, 둘의 절댓값 차를 구한다면 |cnt - (length - cnt)|이므로 정리하면 |2 * cnt - length|가 된다.
따라서 해당 값을 answer가 최소로 가지도록 하였다. (Math.min으로 묶어주는게 더 나을 것 같다.)

Python

풀이 코드

def solution(n, wires):
    tree = [[] for _ in range(n + 1)]
    check = [True] * (n + 1)
    check[1] = False
    score = [1] * (n + 1)

    for w1, w2 in wires:
        tree[w1].append(w2)
        tree[w2].append(w1)

    def getScore(p):
        for c in tree[p]:
            if check[c]:
                check[c] = False
                score[p] += getScore(c)
        return score[p]

    getScore(1)
    return min(abs(score[i] * 2 - n) for i in range(1, n + 1) if score[i])

해석

def getScore(p):
    for c in tree[p]:
        if check[c]:
            check[c] = False
            score[p] += getScore(c)
    return score[p]

현재 노드와 연결된 노드를 내가 방문했는지 체크. 방문하지 않았었다면 재귀를 통해 하위 노드 갯수를 반환하게끔 한다.

return min(abs(score[i] * 2 - n) for i in range(1, n + 1) if score[i])

최솟값을 구하도록 한다. Java 풀이 참고.

여담

해당 방식들은 최솟값을 이미 구했음에도 or 구할 수 있음에도 불구하고 다른 노드까지 다 둘러보게 되는데, 만약 노드가 엄청 많은 경우에는 flag로 추가적인 백트래킹 코드 혹은 다른 풀이가 필요할 듯 싶다.