[프로그래머스-java] Lv.2 전력망을 둘로 나누기

알고리즘 : DFS

---

문제 설명

 

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

프로그래머스

 

---

내 풀이

 

-> 가장 직관적인 풀이 + 효율성은 떨어짐

 

전력망을 둘로 나눈다는 개념에서 보면 결국 2개의 서브트리의 노드의 갯수 차이를 최소화하는 목표의 문제다.
처음에는 DFS만으로 서브트리를 나눠가면서 백트래킹으로 풀려고 했으나 실패했고(이게 더 좋은 풀이)
결국 가장 간단하게 생각 할 수있는 간선을 끊어버리고 DFS를 진행하는 방식을 택했다.
간선을 끊어 낸 다음에 DFS를 진행하면 결국 서브트리의 노드수가 count되고,
전체 n에서 count를 빼면 그게 또 다른 서브트리의 노드수가 되므로,
두개의 서브트리의 뺄셈을 할 경우 그게 차이값이 된다.
이 차이값의 MIN을 찾아가는 과정

 

시간 복잡도
내 풀이에서는 시간복잡도가 좋지는 않다.
(wire의 갯수 * 노드의 수) 이므로 최악의 경우 V^2이 되어버린다.
이것보다 더 좋게 DFS한번으로 끝내는 풀이도 있다.

import java.util.*;

class Solution {
    private static int N;
    private static int count;
    private static boolean[] visited;
    private static ArrayList<Integer>[] adj;

    private static void dfs(int now){
        if (!visited[now]) visited[now] = true;
        count++;

        for (int next : adj[now]){
            if (!visited[next]){
                dfs(next);
            }
        }
    }
    private static void init(){
        count = 0;
        visited = new boolean[N+1];
    }
    public int solution(int n, int[][] wires) {
        N = n;
        adj = new ArrayList[N+1];
        int answer = Integer.MAX_VALUE;

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

        for (int[] edge : wires){
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);

        }

        for (int[] edge : wires) {
            // 간선 제거 
            adj[edge[0]].remove(Integer.valueOf(edge[1]));
            adj[edge[1]].remove(Integer.valueOf(edge[0]));
            // dfs 진행 
            init();
            dfs(edge[0]);

            int subTree = count;
            int remainTree = n - subTree;
            answer = Math.min(answer,Math.abs(remainTree - subTree));

            // 간선 복구
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }


        return answer;
    }
}

더 좋은 풀이

한번의 DFS 즉 시간복잡도 N으로 끝내는 풀이가 있다.
결국 전력망의 구조는 무조건 하나의 트리이고, 두개의 서브트리의 차는 사실 한개의 전력망을 구한다음 전체에서 2번빼면된다.
그러므로 DFS로 자식의 갯수를 전부 탐색하면서 최솟값을 갱신하는 것

전체노드 - 자식트리의 노드수 * 2 이 식의 절대값이 가장 작은 것을 찾으면 된다.

import java.util.*;

class Solution {
    public static int N;
    public static boolean[] visited;
    public static int answer;
    public static ArrayList<Integer>[] adj;

    public int solution(int n, int[][] wires) {
        answer = Integer.MAX_VALUE;
        N = n;
        visited = new boolean[N+1];

        adj = new ArrayList[N+1];
        for(int i = 0; i<=N;i++){
            adj[i] = new ArrayList<>();
        }
        for (int [] edge : wires){
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        dfs(1);
        return answer;
    }
    private static int dfs(int now){
        if (!visited[now]) visited[now] = true;
        int sum = 0;

        for (int next : adj[now]){
            if (!visited[next]){
                // 자식 노드의 수 
                int cnt = dfs(next);
                answer = Math.min(answer,Math.abs(N - cnt*2));
                sum+=cnt;
            }
        } 

        return sum+1;
    }
}