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

1. 문제 소개

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

프로그래머스

문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한 사항
n은 2 이상 100 이하인 자연수입니다.
wires는 길이가 n-1인 정수형 2차원 배열입니다.
wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
1 ≤ v1 < v2 ≤ n 입니다.전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

2. 문제 해석 및 아이디어

1. 전선을 끊은 송전탑에 이어진 송전탑들만 확인하면, 나머지는 n - (이어진 송전탑의 수) 로 쉽게 구할 수 있다.
2. 각각 송전탑의 연결성을 표현해주기 위하여, 인접 리스트를 이용한다.
3. 완전탐색을 통하여 어떠한 전선을 잘랐을 때 가장 절댓값이 적은지 파악한다.

3. 문제 풀이

ArrayList <Integer> [] list = new ArrayList[n + 1];
int answer = Integer.MAX_VALUE;
int count = 0;
for (int[] wire : wires) {
    if (list[wire[0]] == null) 
        list[wire[0]] = new ArrayList<>();
    
    if (list[wire[1]] == null) 
        list[wire[1]] = new ArrayList<>();
    
    list[wire[0]].add(wire[1]);
    list[wire[1]].add(wire[0]);
}

ArrayList 배열을 만들어 줌으로써 인접 리스트를 생성할 수 있다.

주어진 wire 배열을 이용하여 각 노드(송전탑)들을 양방향으로 연결해준다.

ArrayList의 초기화를 위한 overhead를 줄이기 위해 해당 배열 값이 null일 경우 ArrayList를 Initializing 해주는 방식을 이용하였다.

 

for (int[] wire : wires) {
    count = 0;
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(wire[0]);
    visited[wire[1]] = true;
    while(!queue.isEmpty()) {
        Integer target = queue.poll();
        visited[target] = true;
        count++;
        for (int i = 0; i < list[target].size(); i++) {
            if(!visited[list[target].get(i)]) queue.offer(list[target].get(i));
        }
    }
    answer = Math.min(Math.abs((n-count) - count), answer);
}

Queue를 이용하여 BFS 방식으로 그래프를 순회하였다.

절단 할 wire를 for문을 통하여 각각 하나씩 가져온 후, 해당 노드(송전탑)을 Queue에 넣어준다.

wire[0]의 노드와 wire[1]의 노드는 서로 절단되었으니, 만나지 않게 하기 위하여 visited를 true로 변경해주었다.

 

그래프를 순회하기 위해 Queue에서 노드(송전탑)을 poll 하고, visited를 true로 변경해준다.

연결 되어 있다는 의미의 count를 증가시켜주고, 해당 노드(송전탑)에 연결 되어있고, 순회하지 않은 노드(송전탑)을 Queue에 넣어준다. 

 

전체 송전탑은 서로 트리 형태로 연결 되어 있었으니, 절단 된 송전탑들의 개수를 빼주고, 가장 작은 값을 출력해준다.

4. 전체 코드 보기

import java.util. *;

class Solution {
    public int solution(int n, int[][] wires) {
        ArrayList < Integer > [] list = new ArrayList[n + 1];
        int answer = Integer.MAX_VALUE;
        int count = 0;
        for (int[] wire : wires) {
            if (list[wire[0]] == null) 
                list[wire[0]] = new ArrayList<>();
            
            if (list[wire[1]] == null) 
                list[wire[1]] = new ArrayList<>();
            
            list[wire[0]].add(wire[1]);
            list[wire[1]].add(wire[0]);
        }
        for (int[] wire : wires) {
            count = 0;
            boolean[] visited = new boolean[n + 1];
            Queue < Integer > queue = new LinkedList<>();
            queue.add(wire[0]);
            visited[wire[1]] = true;
            while (!queue.isEmpty()) {
                Integer target = queue.poll();
                visited[target] = true;
                count ++;
                for (int i = 0; i < list[target].size(); i ++) {
                    if (!visited[list[target].get(i)]) 
                        queue.offer(list[target].get(i));
                    
                }
            }
            answer = Math.min(Math.abs((n - count) - count), answer);
        }
        return answer;
    }
}

5. 후기

처음에 각 배열의 인덱스에 ArrayList를 Initializing 해주기 위해 for문을 사용하고, 끊어진 노드를 표현하기 위해 해당 인덱스를 서로 제거해주는 방식으로 구현했다.

그렇게 되면 원본 리스트가 변경되기 때문에 Arrays.copyOf() 메소드를 이용하여 원본 리스트를 보존 시켜줘야 했다.

단순한 Initializing 작업에 대한 오버헤드나, 리스트를 복사 하면서 발생하는 오버헤드를 최대한 줄이기 위해 위와 같은 방식으로 풀게 되었다.