프로그래머스 - 전력망을 둘로 나누기 (Java, 완전 탐색, bfs)

아이디어

1. 연결된 노드 리스트 생성

2. 간선 제거

3. bfs 탐색

연결된 노드 리스트 생성

양방향 연결임에 주의하며, 특정 노드에 연결된 모든 노드들에 대한 리스트를 생성하여 map에 담아주었다.

간선 제거

wire들을 순차적으로 탐색하며, 현재 인덱스에 대한 wire를 제거한다.

이는 곧 연결된 두 노드의 각각의 리스트로부터 반대쪽 노드를 제거하는 것과 같다.

유의

remove(index) : 리스트에서 특정 index에 해당하는 값 제거

remove(Integer.valueOf(value) : 리스트에서 특정 value 제거

bfs 탐색

트리에서 하나의 간선을 끊게 되면, 반드시 2개의 트리로 분리된다.

한 쪽 트리에 대해서만 탐색을 하면 나머지 트리에 속한 노드 수도 자연스럽게 알 수 있다.

먼저 시작 노드를 정해주었고, 시작 노드를 큐에 넣어서 bfs 탐색을 해주었다.

map을 사용하여 연결된 노드들을 모두 큐에 넣고 탐색을 진행했다.

마지막으로 방문한 노드에 대해서 cnt를 증가시켜주었다.

(n - cnt) - cnt의 절대값이 두 트리 간의 노드 수 차이가 된다.

import java.util.*;

class Solution {
    boolean[] visit = null;
    Map<Integer, List<Integer>> m = new HashMap<>();


    public int solution(int n, int[][] wires) {
        int answer = n, start = 0;
        visit = new boolean[n];

        for(int i = 0; i < wires.length; i++){
            m.put(wires[i][0], m.getOrDefault(wires[i][0], new ArrayList<>()));
            m.get(wires[i][0]).add(wires[i][1]);
            m.put(wires[i][1], m.getOrDefault(wires[i][1], new ArrayList<>()));
            m.get(wires[i][1]).add(wires[i][0]);
        }

        for(int i = 0; i < wires.length; i++) {
            Arrays.fill(visit, false);

            if(i == 0) start = wires[1][0];
            else start = wires[i - 1][0];

            m.get(wires[i][0]).remove(Integer.valueOf(wires[i][1]));
            m.get(wires[i][1]).remove(Integer.valueOf(wires[i][0]));


            bfs(start);
            int cnt = 0;
            for(int j = 0; j < n; j++) if(visit[j]) cnt++;

            answer = Math.min(answer, Math.abs(n - cnt - cnt));

            m.get(wires[i][0]).add(Integer.valueOf(wires[i][1]));
            m.get(wires[i][1]).add(Integer.valueOf(wires[i][0]));
        }

        return answer;
    }

    public void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visit[start - 1] = true;

        while(!q.isEmpty()){
            int cur = q.poll();
            List<Integer> tmp = m.get(cur);

            for(Integer nxt : tmp) {
                if(visit[nxt - 1]) continue;
                visit[nxt - 1] = true;
                q.add(nxt);
            }
        }
    }
}