전력망을 둘로 나누기

작성일: 2024-10-30

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

접근 방식

인접 리스트를 이용하여, 송전탑과 전력망을 잇는다.

이어진 송전탑들을, 한 부분씩 모두 끊어본다.

끊고 나서, 나누어진 송전탑의 개수의 차이를 구해서 answer보다 작은 경우 업데이트한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer =n;
        LinkedList<Integer> list[] = new LinkedList[n+1];
        // 리스트 초기화
        for(int i=1; i<=n; i++) {
            list[i] = new LinkedList();
        }
        // 송전탑 연결
        for(int[] wire:wires){
            list[wire[0]].add(wire[1]);
            list[wire[1]].add(wire[0]);
        }

        for(int[] wire:wires){
            // 끊을 전선 선택
            int start = wire[0];
            int end = wire[1];

            // 전선 끊기
            list[start].remove((Integer)end);
            list[end].remove((Integer)start);

            int cnt = bfs(list, start, n); // start와 연결된 송전탑 수
            int tmp = Math.abs(cnt - (n-cnt)); // 나누어진 송전탑과의 차이
            answer = Math.min(tmp, answer);

            list[start].add(end);
            list[end].add(start);
        }

        return answer;
    }


    // 연결된 송전탑 개수 확인
    private int bfs(LinkedList<Integer>[] list, int start, int n){
        int cnt = 1;
        boolean visited[] = new boolean[n+1];
        Queue<Integer> que = new LinkedList<>();
        que.offer(start);
        visited[start] = true;

        while(!que.isEmpty()){
            int cur = que.poll();
            for(int l:list[cur]){
                if(!visited[l]){
                    que.offer(l);
                    visited[l] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

다른 접근 방식

인접 리스트를 이용하지 않고, 2차원 배열을 이용해서 서로 이어졌는지 여부를 판단하는 방법이 있었다.

import java.util.*;

class Solution {
    static boolean[][] con;

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

        con = new boolean[n+1][n+1];

        // 송전탑 연결
        for(int[] wire : wires){
            con[wire[0]][wire[1]] = true;
            con[wire[1]][wire[0]] = true;
        }

        for(int[] wire : wires){
            // 전선 끊기
            con[wire[0]][wire[1]] = false;
            con[wire[1]][wire[0]] = false;

            int cnt = bfs(wire[0], n); // wire[0]과 연결된 송전탑 수
            int diff = Math.abs(cnt - (n-cnt)); // 나누어진 송전탑과의 차이

            answer = Math.min(diff, answer);

            // 다시 연결
            con[wire[0]][wire[1]] = true;
            con[wire[1]][wire[0]] = true;
        }

        return answer;
    }

    // 연결된 송전탑 개수 확인 (BFS 사용)
    private int bfs(int start, int n){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        int count = 1;

        while(!queue.isEmpty()){
            int current = queue.poll();
            for(int i = 1; i <= n; i++){
                if(con[current][i]){
                    queue.offer(i);
                    visited[i] = true;
                    count++;
                }
            }
        }

        return count;
    }
}

바뀐 곳은 크게 세 부분이다.

1. 송전탑 연결을 boolean 배열을 이용한다.

2. 연결은 true, 비연결은 false로 나타낸다.

3. 가지 않았던, 송전탑의 판별을 위한 boolean 배열이 필요하다.

알게 된 점

일반적으로 그래프 문제에서, 노드와 간선을 표현하는데 인접 리스트를 많이 떠 올릴 수 있겠지만

boolean 배열을 통한 연결 및 방문 체크도 가능하다.

그래도 생각하기 쉬운 것 개인적으로 인접 리스트가 훨씬 쉬운 것 같다.