[Programmers] 전력망을 둘로 나누기 - Java

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

프로그래머스

---

1. 문제

트리형태로 N개의 송전탑이 주어진다. 이 연결된 전선들 중 하나를 끊어서 네트워크를 2개로 분할하려고 한다.

분할된 두 네트워크가 갖는 송전탑의 개수의 차의 절댓값이 최소가될 때의 절댓값을 리턴한다.

 

2. 풀이

bfs로 풀었다.

이 문제는 제한사항을 잘 읽어야 한다. wires는 길이가 n-1인 정수형 2차원 배열이다.

 

아래와 같은 로직으로 풀었다.

0. min은 Integer.MAX_VALUE로 최댓값으로 초기화한다.

for문을 돌려

1. 연결을 하나씩 끊은 후

2. 2개의 네트워크에서 각각 bfs를 돌려 노드 개수를 구한다.

3. 두 개수의 차의 절댓값과 min을 비교해 min을 갱신한다.

4. 끊었던 연결을 다시 연결시킨다.

 

3. 코드

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

class Solution {
    
    static int min, N, matrix[][];
    
    public int solution(int n, int[][] wires) {
        N = n;
        matrix = new int[N+1][N+1];
        
        for (int i=0; i<N-1; i++) {
            matrix[wires[i][0]][wires[i][1]] = 1;
            matrix[wires[i][1]][wires[i][0]] = 1;
        }
        
        min = Integer.MAX_VALUE;
        for (int i=0; i<N-1; i++) {
            int s1 = wires[i][0];
            int s2 = wires[i][1];
            // 연결 끊음
            matrix[s1][s2] = 0;
            matrix[s2][s1] = 0;
            
            int cnt1 = bfs(s1);
            int cnt2 = bfs(s2);
            min = Math.min(min, Math.abs(cnt1-cnt2));
            
            // 다시 연결
            matrix[s1][s2] = 1;
            matrix[s2][s1] = 1;
        }
        return min;
    }
    
    static int bfs(int num){
        Queue<Integer> queue = new ArrayDeque<> ();
        boolean[] visited = new boolean[N+1];
        
        queue.offer(num);
        visited[num] = true;
        int cnt = 0;
        
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int i=1; i<=N; i++) {
                if (now==i || matrix[now][i] == 0 || visited[i] == true) continue;
                queue.offer(i);
                visited[i] = true;
                cnt++;
            }
        }
        return cnt;
    }
}

 

4. 사담

그래프 문제는 재밌는 것 같다.