[프로그래머스/Java] 86971 전력망을 둘로 나누기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

🔍  해결 과정

송전탑의 개수의 최대 크기는 100이므로 완전 탐색의 방식을 활용하여 송전탑마다 연결되어 있는 전선의 개수를 하나하나 끊어가며 두 개의 전력망으로 구성이 되었을 때 송전탑의 개수의 차이를 비교해주었습니다. 자세한 과정은 다음과 같습니다.

1️⃣ 트리로 구성되어 있는 송전탑 전용 그래프 변수를 만들어준다. (그래프의 사이즈는 n + 1로 설정했다.)
2️⃣  wires를 활용하여 그래프 연결 정보를 업데이트한다.
3️⃣ 다시 wires를 활용하여 전선을 끊었을 때 각 전력망의 송전탑 개수를 bfs(Breadth-First Search)를 활용하여 구해준다.
4️⃣ 3번을 반복하며 두 전력망의 송전탑의 개수 차이의 최솟값을 찾아낸다.

 

---

✏️ 코드

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] wires) {
        int answer = (int) 1e9;
        List<Integer>[] graph = new ArrayList[n + 1];
        
        for (int i = 0; i <= n; ++i) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] wire : wires) {
            graph[wire[0]].add(wire[1]);
            graph[wire[1]].add(wire[0]);
        }
        
        // wire을 하나씩 다시 살펴보며 하나씩 끊어보기
        for (int[] wire : wires) {
            int diff = resultRemoveWire(graph, wire[0], wire[1]);
            
            if (answer > diff) {
                answer = diff;
            }
        }

        return answer;
    }
    
    private int resultRemoveWire(final List<Integer>[] graph, final int w1, final int w2) {
        int len = graph.length;
        List<Integer>[] graphTemp = new ArrayList[len];
        
        for (int i = 0; i < len; ++i) {
            graphTemp[i] = new ArrayList<>(graph[i]); // 깊은 복사
        }
        
        graphTemp[w1].remove(Integer.valueOf(w2)); // 객체형 Integer로 변환해서 직접 값을 제거
        graphTemp[w2].remove(Integer.valueOf(w1));
        
        // bfs 진행하기
        return Math.abs(bfs(graphTemp, w1) - bfs(graphTemp, w2));
    }
    
    private int bfs(List<Integer>[] graphTemp, int start) {
        boolean[] visited = new boolean[graphTemp.length];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;
        int count = 1;
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            for (int i = 0; i < graphTemp[cur].size(); ++i) {
                int next = graphTemp[cur].get(i);
                
                if (visited[next]) {
                    continue;
                }
                
                ++count;
                visited[next] = true;
                q.offer(next);
            }
        }
        
        return count;
    }
}