Programmers_86971.java

package programmers.lv2;

import java.util.ArrayList;

public class Programmers_86971 {
    public static void main(String[] args) {
        Programmers_86971 test = new Programmers_86971();
        int n = 9;
        int[][] wires = { { 1, 3 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 7, 8 }, { 7, 9 } };
        int result = test.solution(n, wires);
        System.out.println("result: " + result);
    }

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 세팅
        for (int i = 0; i < wires.length; i++) {
            int node1 = wires[i][0];
            int node2 = wires[i][1];

            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }

        // 전선 끊기
        for (int i = 0; i < wires.length; i++) {
            int node1 = wires[i][0];
            int node2 = wires[i][1];

            graph.get(node1).remove(Integer.valueOf(node2));
            graph.get(node2).remove(Integer.valueOf(node1));

            boolean[] visited = new boolean[n + 1];
            int nodeSum1 = dfs(graph, node1, visited);
            int nodeSum2 = dfs(graph, node2, visited);
            answer = Math.min(answer, Math.abs(nodeSum1 - nodeSum2));

            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }

        return answer;
    }

    private int dfs(ArrayList<ArrayList<Integer>> graph, int idx, boolean[] visited) {
        visited[idx] = true;
        int count = 1;

        ArrayList<Integer> node_list = graph.get(idx);
        for (Integer node : node_list) {
            if (!visited[node]) {
                count += dfs(graph, node, visited);
            }
        }

        return count;
    }
}