[프로그래머스] 전력망을 둘로 나누기(Java)

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

프로그래머스

 

---

문제 풀이

1. 끊어진 선에 따른 인접리스트를 생성해준다. 

2. 인접리스트를 사용해 완전탐색(BFS) 수행

3. BFS 수행 후, 방문 영역(true)와 미방문 영역(false)를 나눈다. -> 각 area1, area2로

4. area1과 area2의 차이 중, 최솟값을 answer에 넣어준다.

import java.util.*;

class Solution {

    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static int n;
    static int answer;

    public int solution(int num, int[][] wires) {
        answer = Integer.MAX_VALUE;
        n = num;
        
        for(int i=0; i<wires.length; i++) {
            makeGraph(i, wires); // i : 끊긴 선
        }
		
        return answer;
    }
	
    public void makeGraph(int brokenWire, int[][] wires) {
        // 방문 배열 초기화
        visited = new boolean[n+1];
			
        // 인접리스트 초기화
        arr = new ArrayList[n+1];
        for(int i=0; i<=n; i++) {
            arr[i] = new ArrayList<Integer>();
        }
        
        // 끊긴 선을 제외하고 인접리스트 생성
        for(int i=0; i<wires.length; i++) {
            if(i != brokenWire) {
                int s = wires[i][0];
                int e = wires[i][1];
                arr[s].add(e);
                arr[e].add(s);
            }
        }
        
        BFS(1);
    }
	
    public void BFS(int node) {
            int area1 = 0;
	    Queue<Integer> q = new LinkedList<>();
		
		q.add(node);
		visited[node] = true;
		
		while(!q.isEmpty()) {
		   int newNode = q.poll();
            
		   for(int i=0; i<arr[newNode].size(); i++) {
		      if(!visited[arr[newNode].get(i)]) {
			      visited[arr[newNode].get(i)] = true;
				  q.add(arr[newNode].get(i));
			  }
		   }
		}
        
        for(int i=1; i<=n; i++) {
            if(visited[i]) {
                area1++;
            }
        }
        
        int area2 = n - area1;
        answer = Math.min(answer, Math.abs(area1 - area2));
    }
}