전력망을 둘로 나누기

사용 알고리즘: bfs

사용 언어: java

 

import java.util.*;
import java.io.*;

class Solution {
    static int answer = 100; //n은 100이하
    static ArrayList<Integer>[] tree; 
    
    public static int solution(int n, int[][] wires) {
        ArrayList<Integer>[] tree; 
        tree = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            tree[i] = new ArrayList<Integer>();
        }
        
        for(int i=0; i<wires.length; i++) {
            tree[wires[i][0]].add(wires[i][1]);
            tree[wires[i][1]].add(wires[i][0]);
        }
        
        for(int i=0; i<wires.length; i++) {
            tree[wires[i][0]].remove(Integer.valueOf(wires[i][1]));
            tree[wires[i][1]].remove(Integer.valueOf(wires[i][0]));
            
            boolean[] visited = new boolean[1+n];
            visited[1] = true;
            
            int firstGroup = bfs(1, n, visited, tree, answer);
            int gap = Math.abs(firstGroup - (n - firstGroup));
            answer = Math.min(answer, gap);
            
            tree[wires[i][0]].add(wires[i][1]);
            tree[wires[i][1]].add(wires[i][0]);
        }
        
        return answer;
    }
    
    public static int bfs(int start, int n, boolean[] visited, ArrayList<Integer>[] tree, int answer) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        int firstGroup = 1;
        
        while(!q.isEmpty()) {
            int p = q.poll();
            for(int i : tree[p]) {
                if(!visited[i]) {
                    firstGroup++;
                    visited[i] = true;
                    q.offer(i);
                }
            }
        }
        
        return firstGroup;
        
    } //bfs
}

 

 

이슈:

static 어쩌구 에러... 

둘 사이의 차이는 (한 그룹의 개수)와 (전체 - 한 그룹의 개수)!!