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

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

프로그래머스

 

 

import java.util.*;
class Solution {
    static ArrayList<Integer>[] graph;
    static int min;
    public int solution(int n, int[][] wires) {
        graph = new ArrayList[n+1];
        min = Integer.MAX_VALUE;
        
        //노드 초기화
        for(int i=1;  i<=n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i<wires.length; i++){
            int a = wires[i][0];
            int b = wires[i][1];
            graph[a].add(b);
            graph[b].add(a);
        }
        
        for(int i=0; i<wires.length; i++){
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            boolean[] visited = new boolean[n+1];
            
            //해당 간선을 그래프에서 제거해야 함
            graph[v1].remove(Integer.valueOf(v2));
            graph[v2].remove(Integer.valueOf(v1));
            
            int cnt = dfs(1,visited); //노드 1부터 탐색 시작
            
            int diff = Math.abs(cnt - (n-cnt));
            min = Math.min(min,diff);
            
            graph[v1].add(v2);
            graph[v2].add(v1);
             
        }
        

        return min;
    }
    
    static int dfs(int v, boolean[] visited){
        visited[v]=true;
        int cnt=1;
        for(int next: graph[v]){
            if(!visited[next]){
                cnt += dfs(next,visited);
            }
        }
        return cnt;
    }
}

우선 graph를 만들기 위해 ArrayList배열을 만들어야 한다.

n만큼 ArrayList를 만들어 노드를 기입할 수 있게 한다.

 

여기서 중요한 점은 

원하는 노드를 그래프에서 삭제할 때 이다.

graph[v1].remove(Integer.valueOf(v2))

ArrayList에서 remove하려면 remove(Object o)  함수를 써야한다.

graph[v1].remove(v2)가 아닌 Integer객체를 넣어주어야 제대로 동작한다.

 

그렇게 제거하고 dfs를 돌려 노드 수를 세어준다.

 

 

 

 

참조

https://hianna.tistory.com/564