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

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 전력망을 둘로 나누기

 

문제의 입력은 무조건 트리 형태로 주어집니다.
= 순환 사이클이 없다 = 무조건 루트가 1인 트리 형태로 재배열할 수 있다.

주어진 예제의 경우 다음과 같다.

이렇게 트리 형태로 만들었을 때, 어떻게 가장 차이가 적게 나눌 수 있는가?

자신을 포함한 서브트리의 크기를 계산해서 비교해주면 됩니다.

서브트리의 크기는 dfs로 구할 수 있습니다.

일단 노드가 n개 주어지기 때문에 최대 크기는 n일 것입니다.

그리고  dfs를 진행하는데,
맨 왼쪽의 예제의 경우 1의 서브트리의 크기 = 1+3서브트리 크기
3서브트리 크기=1+2서브트리+4서브트리
4서브트리=1+5서브트리+7서브트리+6서브트리

이런식으로 자식 노드들을 재귀로 탐색해가면서 더해주면 현재 서브트리의 크기를 구할 수 있다.

차이가 가장 적게 하는 전선을 하나 끊어야하는데 그 전선이 뭔지는 알 필요 없고 사이즈의 차이만 비교하면 되기 때문에 섭트리를 진행할때마다 전체 크기와 서브트리의 크기를 비교해주면서 답을 찾으면 됨

 

import java.util.*;

class Solution {
    
    private static boolean[] visit;
    private static List<Integer>[] adj;
    private static int min;
    
    public int solution(int n, int[][] wires) {

		visit = new boolean[n + 1];
		adj = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < n - 1; i++) {
			adj[wires[i][0]].add(wires[i][1]);
			adj[wires[i][1]].add(wires[i][0]);
		}

		min = n;
		dfs(1, n);
		return min;
	}

	private static int dfs(int node, int n) {
		visit[node] = true;
		int size = 1;
		for (int next : adj[node]) {
			if (visit[next])
				continue;

			size += dfs(next, n);
		}

		min = Math.min(min, Math.abs(n - 2 * size));
		return size;
	}
}