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

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

프로그래머스

---

접근 방식

 

하나로 연결되어 있는 전력망을 전선을 하나 잘라서 두 개의 전력망으로 나눌 것이다. 아래 그림처럼 자르는 전선이 만약에 [4, 7] 이라고 한다면 두 전력망은 4에 연결되어 있는 전력망과 7에 연결되어 있는 전력망으로 나눠질 것이다.

4에 연결되어 있는 전력망의 송전탑의 개수는 6개이고, 7에 연결되어 있는 전력망의 송전탑의 개수는 3개이다.

 

어떤 송전탑에 연결되어 있는 송전탑의 개수는 dfs / bfs 로 구할 수 있다. dfs / bfs로 두 송전탑에 연결되어 있는 송전탑의 개수를 구하고 두 값의 차를 구하면 된다.

 

그럼 모든 전선들에 대해서 전선을 잘랐을 때의 경우를 모두 구하고 결과(송전탑 개수의 차이)의 최솟값을 구하면 될 것이다.

 

풀이는 코드에 주석으로 달아놓았다!

---

전체코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        
        for(int i=0; i<wires.length; i++){
            int tower1 = wires[i][0];
            int tower2 = wires[i][1];
            
            // i번째 wire를 자른(제외한) 그래프
            boolean[][] graph = makeGraph(wires, i, n);
            
            // 각각 tower1과 tower2에 연결되어 있는 송전탑의 개수를 구함
            int cnt1 = bfs(graph, tower1);
            int cnt2 = bfs(graph, tower2);
            
            // 두 전력망의 송전탑 개수의 차의 최솟값
            answer = Math.min(answer, Math.abs(cnt1 - cnt2));
        }
        
        return answer;
    }
    
    // graph 에서 start에 연결되어 있는 송전탑의 개수 구하는 함수
    // bfs로 구현함
    int bfs(boolean[][] graph, int start){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        
        // 자기 자신
        int cnt = 1;
        
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()){
            int tower = q.poll();
            
            // 현재 송전탑인 tower에 연결되어 있는 탑의 개수 구하기
            for(int i=0; i<graph[tower].length; i++){
            	// graph[tower][i]가 true 라면 tower번과 i번은 연결되어 있는 송전탑
                if(graph[tower][i] && !visited[i]){
                    q.offer(i);
                    visited[i] = true;
                    cnt ++;
                }
            }
        }
        
        return cnt;
    }
    
    // idx 번째 wire를 제외한 그래프 그리기
    boolean[][] makeGraph(int[][] wires, int idx, int n){
        // wires의 길이는 n-1이니까 graph의 길이는 n+1 = n-1 + 2 (0~n)
        boolean[][] graph = new boolean[wires.length + 2][wires.length + 2];

        for(int i=0; i<wires.length; i++){
            // idx 번째 wire는 자름
            if(i == idx) continue;

            int tower1 = wires[i][0];
            int tower2 = wires[i][1];

            // 양방향 연결
            graph[tower1][tower2] = true;
            graph[tower2][tower1] = true;
        }

        return graph;
	}
}