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

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

문제

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

프로그래머스

문제 분석

조건

• 하나의 트리형 전력망이 있다 (노드 + 간선)
• 전선을 하나 끊어서 두 개의 네트워크로 나눌 수 있는데 이때 두 네트워크의 노드 수 차이를 최소로 만들어 차이를 출력

풀이방법

• 트리를 입력받은 후 간선마다 돌아가며 DFS를 수행하면 된다.
• 하나의 트리로 연결되어있고, 전체 노드의 수를 알고 있으므로 간선의 두 노드 중 하나에서만 DFS를 돌리면 나머지 네트워크의 노드 수도 알 수 있다.

코드

import java.util.*;

class Solution {
    static List<Integer>[] tree;
    static boolean[] visited;

    public int solution(int n, int[][] wires) {
        int answer = 101;
        tree = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int[] wire : wires) {
            tree[wire[0]].add(wire[1]);
            tree[wire[1]].add(wire[0]);
        }
        visited = new boolean[n + 1];
        for (int[] wire : wires) {
            Arrays.fill(visited, false);
            visited[wire[0]] = true;
            visited[wire[1]] = true;
            answer = Math.min(Math.abs(dfs(wire[0]) * 2 - n), answer);
            if (answer == 0) {
                break;
            }
        }
        return answer;
    }

    private int dfs(int now) {
        int count = 1;
        for (Integer next : tree[now]) {
            if (visited[next]) {
                continue;
            }
            visited[next] = true;
            count += dfs(next);
        }
        return count;
    }
}