[그래프] 프로그래머스 전력망을 둘로 나누기 // 자식수 세기는 dfs, 직접나누지말고 자식수를 계산하라

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

프로그래머스

 

* 풀이1

직접 연결을 1개씩 지운후 탐색하는 방법

tip) 2차원 행렬그래프 => 쉽게 연결정보 삭제가능

2차원 인접리스트 => 삭제,복원 어려움

import java.util.*;

class Solution {
    static ArrayList<Integer>[] adj = new ArrayList[104];
    static int[][] graph = new int[104][104];
    static boolean[] vis = new boolean[104];
    static int n;
    
    int dfs(int node){
        vis[node]=true;
        
        int ret=1;
        for(int i=1;i<=n;++i){
            if(vis[i]) continue;
            
            if(graph[node][i]==1){
                ret+=dfs(i);
            }
        }
        return ret;
        
    }
    
    public int solution(int N, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        n=N;
        for(int i=0;i<104;++i){
            adj[i]=new ArrayList<>();
        }
        for(var wire : wires){
            int from = wire[0];
            int to  = wire[1];
            adj[from].add(to);
            adj[to].add(from);
            graph[from][to]=1;
            graph[to][from]=1;
        }
        // for(int i=1;i<n;++i){
        //     System.out.println(adj[i]);
        // }
        
        // 연결끊을 index 고르기
        // 연결끊기
        // dfs
        // 원상복구
        for(int i=0;i<wires.length;++i){
            int from = wires[i][0];
            int to = wires[i][1];
            
            graph[from][to]=0;
            graph[to][from]=0;
            
            Arrays.fill(vis,false);
            var v = new ArrayList<Integer>();
            for(int j=1;j<=n;++j){
                if(vis[j]) continue;
                
                v.add(dfs(j));
            }
            
            graph[from][to]=1;
            graph[to][from]=1;
            
            // System.out.println(v.get(0) +" " + v.get(1));
            answer = Math.min(answer,Math.abs(v.get(0)-v.get(1)));
        }
        return answer;
    }
}

 

* 풀이2

연결을 제거X,

자식수를 세고, 그때그떄 분리하면서 정답갱신

리프노드에서 ret 1 되는것부터 해봐야 한다.

return 되기 직전에 그래프를 나누고 정답을 갱신한다.

(n-child) - child 의 식을 도출해야 한다.

 

* 코드

import java.util.*;

class Solution {
    static ArrayList<Integer>[] adj = new ArrayList[104];
    static int[][] graph = new int[104][104];
    static boolean[] vis = new boolean[104];
    static int n;
    static int answer = Integer.MAX_VALUE;
    
    int dfs(int node){
        vis[node]=true;
        
        int child=1; // 자기자신 카운팅
        
        for(var nxt : adj[node]){
            if(vis[nxt]) continue;
            
            child+=dfs(nxt);
        }
        
        answer = Math.min(answer,Math.abs((n-child)-child));
        return child;
    }
    
    public int solution(int N, int[][] wires) {
        
        n=N;
        for(int i=0;i<104;++i){
            adj[i]=new ArrayList<>();
        }
        for(var wire : wires){
            int from = wire[0];
            int to  = wire[1];
            adj[from].add(to);
            adj[to].add(from);
        }

        dfs(1);
        
        return answer;
    }
}