[프로그래머스] 전력망을 둘로 나누기_자바

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

프로그래머스

---

송전탑 전선을 하나씩 끊어보면서 가장 적은 차이를 냈을 때를 찾는 것.

BFS를 사용한다.

	public int solution(int n, int[][] wires) {
        int answer = n-1; // 송전탑 개수 최대 차이
        a = new int[n+1][n+1]; 
        for(int i=0; i<wires.length; i++){ // 연결된 송전탑 정보를 행렬에
            int x = wires[i][0];
            int y = wires[i][1];
            a[x][y] = 1; 
            a[y][x] = 1;
        }
        for(int i=0; i<wires.length; i++){
            int x = wires[i][0];
            int y = wires[i][1];

            a[x][y] = 0; // 전선 끊어줌
            a[y][x] = 0;

            answer = Math.min(answer, bfs(n,x)); // 송전탑 차이 최소값

            a[x][y] = 1; // 전선 다시 이어줌
            a[y][x] = 1;
        }
        return answer;
    }

	public static int bfs(int n, int start){
        int[] ch = new int[n+1]; // 방문 노드 확인 배열
        int cnt = 1; // 송전탑 개수는 1개부터 시작
        Queue<Integer> q = new LinkedList<>();
        q.add(start); // 처음 송전탑 번호 큐에 넣음
        while(!q.isEmpty()){
            int tmp = q.poll();
            ch[tmp] = 1;
            for(int i=1; i<=n; i++){
                if(ch[i]==0 && a[tmp][i]==1){ // 현재 송전탑과 연결된 송전탑 찾기
                    q.add(i);
                    cnt++;
                }
            }
        }
        return Math.abs(cnt-(n-cnt)); // 송전탑 개수 차이 리턴
    }

---

[ 전체코드 ]

import java.util.LinkedList;
import java.util.Queue;

public class P6 {
    static int[][] a;
    public static void main(String[] args){
        P6 p = new P6();
        int n = 9;
        int[][] wires = {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}};
        System.out.println(p.solution(n, wires));
    }
    public int solution(int n, int[][] wires) {
        int answer = n-1; // 송전탑 개수 최대 차이
        a = new int[n+1][n+1];
        for(int i=0; i<wires.length; i++){
            int x = wires[i][0];
            int y = wires[i][1];
            a[x][y] = 1;
            a[y][x] = 1;
        }
        for(int i=0; i<wires.length; i++){
            int x = wires[i][0];
            int y = wires[i][1];

            a[x][y] = 0; // 전선 끊어줌
            a[y][x] = 0;

            answer = Math.min(answer, bfs(n,x));

            a[x][y] = 1; // 전선 다시 이어줌
            a[y][x] = 1;
        }
        return answer;
    }
    public static int bfs(int n, int start){
        int[] ch = new int[n+1];
        int cnt = 1;
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        while(!q.isEmpty()){
            int tmp = q.poll();
            ch[tmp] = 1;
            for(int i=1; i<=n; i++){
                if(ch[i]==0 && a[tmp][i]==1){
                    q.add(i);
                    cnt++;
                }
            }
        }
        return Math.abs(cnt-(n-cnt));
    }
}