[알고리즘] 프로그래머스 - 전력망을 둘로 나누기 Lv2 Java BFS

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

프로그래머스

 

package Programmers;

import java.util.*;

public class 전력망을둘로나누기 {
    static int[][] myWires;
    public static void main(String[] args){
        전력망을둘로나누기 T = new 전력망을둘로나누기();
        int n = 9;
        int[][] wires = {{1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9}};
        T.solution(n, wires);
    }
    public int solution(int n, int[][] wires) {
        int answer = n;
        myWires= new int[n+1][n+1];

        //1. 2차원 배열로 인접행렬을 그린다.
        for(int i=0; i<wires.length; i++){
            myWires[wires[i][0]][wires[i][1]]=1;
            myWires[wires[i][1]][wires[i][0]]=1;
        }

        //2. Wires노드 하나씩 삭제해가면서 bfs를 돌린다.
        for (int i = 0; i < wires.length; i++) {
            int a = wires[i][0];
            int b = wires[i][1];
            //노드삭제
            myWires[a][b] = 0;
            myWires[b][a] = 0;
            int rs = bfs(n, a);
            answer = Math.min(answer, rs);
            //노드재추가
            myWires[a][b] = 1;
            myWires[b][a] = 1;

        }
        return answer;
    }

    public int bfs(int n, int s){
        //방문했는지 여부 배열
        int[] ch = new int[n+1];
        int cnt = 1;
        Queue<Integer> q = new LinkedList<>();
        q.offer(s);
        while (!q.isEmpty()){
            int node = q.poll();
            ch[node] = 1;
            for (int i = 0; i <= n; i++) {
                //이미방문한 Node일경우에는 지나친다.
                if(ch[i] == 1) continue;
                //노드가 있는부분만 지나간다.
                if(myWires[node][i] == 1){
                    q.offer(i);
                    cnt++;
                }
            }
        }
        int rs = cnt - (n - cnt);
        return Math.abs(rs);
    }
}

1. 풀이

 1.1 ) myWires에 2차원 배열로 인접 리스트를 생성해준다. [1,3] 일경우 myWires[1][3], myWires[3][1] 부분에 1을 체크해준다. 왕복으로 가능하니까 둘다 체크해주는것.

 1.2 ) for문을 돌면서 wires배열을 순차적으로 노드 하나씩 삭제한다.

    - myWires를 0 으로 체크해준다.

 1.3 ) bfs 탐색으로 노드가 어디까지 연결되어있는지 확인 

    - cnt가 증가하면 이어진 노드로 건너갔단 소리.

    - 구하고자 하는 답이 분리된 노드의 차이니까 총 n개에서 건나간 노드 수만큼 빼주면 분리된 노드의 개수가 나오고 거기서 다시 cnt를 나눠주면 노드의 차를 구할수있음.

 1.4 ) 절대값을 붙여서 최소값을 구하자.

 

※ 2차원 배열로 노드 생성을 생각하는데 시간이좀걸림