99클럽 코테 스터디 24일차 TIL

프로그래머스 - 전력망을 둘로 나누기

풀이

주어진 wires를 모두 한 번씩 끊었을 때 나올 수 있는 각각의 전력망에서,

송전탑의 개수를 비교하여 차이를 반환해야 한다.

 

모든 wires를 끊어보려면 반복을 돌 때마다 전선 환경을 초기화해줘야 한다.

만약 1, 3번 전선을 끊었을 때의 송전탑 차이를 계산했다면

계산한 값을 저장해두고 끊었던 전선을 다시 연결해줘야 한다.

위 과정을 반복해서 송전탑 차이가 가장 적은 값을 반환해 주면 된다.

 

구현

import java.util.*;

class Solution {
    private List<Integer>[] tree;
    private boolean[] visited;

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;

        // 전선 트리 초기화
        tree = new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new LinkedList<>();
        }

        // 전선 연결
        for (int i = 0; i < wires.length; i++) {
            tree[wires[i][0]].add(wires[i][1]);
            tree[wires[i][1]].add(wires[i][0]);
        }

        // 모든 전선을 하나씩 끊었을 때 전력망마다 가지게 되는 송전탑 수를 구한다.
        // 분리된 전력망의 송전탑 차를 구한다.
        // 위 과정을 반복하면서 송전탑 차의 최솟값을 반환한다.
        for (int i = 0; i < wires.length; i++) {
            // 전선 끊기 - 전력망 분리
            tree[wires[i][0]].remove(Integer.valueOf(wires[i][1]));
            tree[wires[i][1]].remove(Integer.valueOf(wires[i][0]));

            // 송전탑 방문 초기화
            visited = new boolean[n + 1];

            // 분리된 전력망의 송전탑 갯수를 구한다.
            int count = bfs(1);
            answer = Math.min(answer, Math.abs(count - (n - count)));

            tree[wires[i][0]].add(wires[i][1]);
            tree[wires[i][1]].add(wires[i][0]);
        }

        return answer;
    }

    private int bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;

        int count = 1;
        while (!queue.isEmpty()) {
            int current = queue.remove();

            for (int node : tree[current]) {
                if (!visited[node]) {
                    visited[node] = true;
                    queue.add(node);
                    count++;
                }
            }
        }

        return count;
    }
}

 

DFS 로 구현한 사례들도 많았지만 사고가 너무 깊어지고 이해하기 힘들어 BFS로 구현했다.

---

프로그래머스 - 전력망을 둘로 나누기

프로그래머스

 

참고

[프로그래머스/Lv. 2] 전력망을 둘로 나누기 (JAVA)

[프로그래머스]level 2: 전력망 둘로 나누기_Java(위클리 9주차)