[프로그래머스/JAVA] 위클리 챌린지 9주차

코딩테스트 연습 - 9주차

 

 

---

 

 

 

• 풀이

 

arraylist 배열을 사용해서 풀었습니다.

 

1. 모든 wires의 왼쪽 노드와 오른쪽 노드를 끊어가며 재귀를 통해 연결된 모든 노드의 개수를 계산해줍니다.

2. 왼쪽 노드와 오른쪽 노드의 차이의 절대값 중 가장 작은 값을 answer에 저장합니다.

 

 

• 코드

 

import java.util.*;

class Solution {
    static ArrayList[] array;
    static boolean[] check;
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        array = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++){
            array[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0 ; i < wires.length; i++) {
            array[wires[i][0]].add(wires[i][1]);
            array[wires[i][1]].add(wires[i][0]);
        }
        
        for(int i = 0 ; i < wires.length; i++) {
            check = new boolean[n+1];
            check[wires[i][0]] = true;
            check[wires[i][1]] = true;
            int a = bfs(wires[i][0]);
            int b = bfs(wires[i][1]);
            answer = Math.min(answer, Math.abs(a-b));
        }
        
        return answer;
    }
    
    private static int bfs(int index) {
        int sum = 1;
        check[index] = true;
        for(int i = 0 ; i < array[index].size(); i++){
            if(check[(int)array[index].get(i)]) continue;
            sum += bfs((int)array[index].get(i));
        }
        
        return sum;
    }
}