[프로그래머스] 전력망 둘로 나누기 - JAVA

 - 링크 : https://programmers.co.kr/learn/courses/30/lessons/86971?language=java# 

코딩테스트 연습 - 9주차_전력망을 둘로 나누기

 

 - 풀이

 : 문제에서 트리가 보장되어 있기 때문에 하나를 끊으면 무조건 둘로 나뉜다.

 : 그리고 노드의 총 갯수가 n이기 때문에 한 쪽을 dfs든 bfs든 돌려서 개수를 구하면 나머지 한 쪽은 n - 한 쪽 개수이다.

 

 이를 이용해서 풀었다.

 

 : for 를 2번 돌면서 edge(간선)가 하나씩 없는 인접 리스트를 각 루프 마다 만들고 bfs를 돌면서 한 쪽의 vertex(정점) 개수를 체크한다.

 : 나머지 한 쪽은 자연스럽게 구해질 것이고 이 둘을 뺀 차 중에 가장 최소값을 구한다.

 

 - 답

 

import java.util.*;

class Solution {
    ArrayList<Integer>[] adj;
    boolean[] visited;
    
    public int solution(int n, int[][] wires) {
        int answer = n+1;
        
        for (int i=0; i < wires.length; i++) {
            visited = new boolean[n+1];
            adj = new ArrayList[n+1];
            for (int j=1; j < n+1; j++) {
                adj[j] = new ArrayList<Integer>();
            }
            
            for (int j=0; j < wires.length; j++) {
                if (j==i) {
                    continue;
                }

                int v1 = wires[j][0];
                int v2 = wires[j][1];
                adj[v1].add(v2);
                adj[v2].add(v1);
            }
            
            int initVal = wires[i][0];
            int firstTreeCount = bfs(initVal);
            int restTreeCount = n - firstTreeCount;
            answer = Math.min(answer, Math.abs(firstTreeCount - restTreeCount));
        }
        
        return answer;
    }
    
    private int bfs(int sNode) {
        visited[sNode] = true;
        int count = 1;
        
        Queue<Integer> q = new LinkedList();
        q.add(sNode);
        
        while(!q.isEmpty()) {
            int cNode = q.poll();
            
            for (int i=0; i < adj[cNode].size(); i++) {
                int nNode = adj[cNode].get(i);
                if (!visited[nNode]) {
                    visited[nNode] = true;
                    count++;
                    q.add(nNode);
                }
            }
        }
        
        return count;
    }
}