catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 전력망을 둘로 나누기

jynn@catsriding.com
Sep 08, 2024
Published byJynn
999
프로그래머스 | Level 2 | 전력망을 둘로 나누기

Programmers | Level 2 | 전력망을 둘로 나누기

Problems

  • 📘 Src: Programmers
  • 🗂️ Cat: Depth-First Search

󰧭 Description

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 Constraints

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

󰦕 Examples

nwiresresult
9[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]3
4[[1,2],[2,3],[3,4]]0
7[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]1

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        // 전체 송전탑 간 연결 상태를 저장하는 그래프
        List<List<Integer>> graph = new ArrayList<>();        
        for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());
        
        // 송전탑들 간의 연결 상태를 그래프에 저장
        for (int[] wire : wires) {
            int node1 = wire[0];
            int node2 = wire[1];
            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }
        
        int minDiff = n;  // 최소 차이를 저장할 변수 초기화
        
        // 모든 전선을 끊어가며 송전탑의 개수 차이를 계산
        for (int[] wire : wires) {
            // 현재 처리 중인 전선의 두 송전탑 노드를 가져오기
            int node1 = wire[0];  // 첫 번째 송전탑 노드
            int node2 = wire[1];  // 두 번째 송전탑 노드
            
            // 두 송전탑 간의 연결을 임시로 끊음
            graph.get(node1).remove((Integer) node2);
            graph.get(node2).remove((Integer) node1);
            
            // 끊긴 상태에서 한 전력망의 송전탑 개수를 구함 (DFS 탐색)
            int count = dfs(graph, new boolean[n + 1], node1);
            
            // 두 전력망의 송전탑 개수 차이를 계산하고 최소값 갱신
            int currentDiff = Math.abs((n - count) - count);
            minDiff = Math.min(currentDiff, minDiff);
            
            // 끊었던 전선 복구
            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }
        
        return minDiff;
    }
    
    // DFS 탐색으로 연결된 송전탑의 개수를 세는 함수
    private int dfs(List<List<Integer>> graph, boolean[] marked, int node) {
        // 현재 송전탑 방문 처리
        marked[node] = true;
        int count = 1;  // 현재 송전탑 카운트
        
        // 현재 송전탑과 연결된 다른 송전탑들 탐색
        for (int next : graph.get(node)) {
            // 이미 방문한 송전탑은 건너뜀
            if (!marked[next]) {
                // 방문하지 않은 송전탑에 대해 재귀적으로 탐색하고 개수를 누적
                count += dfs(graph, marked, next);
            }
        }
        // 연결된 모든 송전탑의 개수를 반환
        return count;
    }
}

 Approach

이 문제는 각각의 전선을 하나씩 끊어서 두 전력망으로 나누고, 각 전력망의 송전탑 개수 차이를 최소화하는 개수를 구하는 문제입니다. 이는 그래프 탐색 문제로, 깊이 우선 탐색(DFS)을 통해 전력망을 탐색하고 개수를 계산할 수 있습니다.

1. 문제 분석

송전탑들이 전선으로 연결된 트리 구조에서, 전선을 하나 끊으면 두 개의 전력망으로 분리됩니다. 목표는 분리된 두 전력망의 송전탑 개수를 최대한 비슷하게 맞추는 것입니다.

전선을 끊을 때마다 두 개의 서브 트리가 형성되고, 각 서브 트리에 속한 송전탑의 개수를 계산한 후, 그 차이를 구해야 합니다. 두 전력망 간의 송전탑 개수 차이의 절대값을 구해, 그 값이 최소가 되도록 해야 합니다.

이를 위해 전선을 하나씩 끊고, 한쪽 서브 트리의 송전탑 개수를 계산한 후, 전체 송전탑 개수에서 그 값을 빼서 나머지 전력망의 송전탑 개수를 구합니다. 이렇게 구한 두 전력망 간의 차이를 반복적으로 비교해, 최소 차이를 찾아내는 것이 핵심입니다.

2. 접근 방식

이 문제는 그래프 탐색을 통해 전선이 끊긴 상태에서 두 전력망으로 나뉘는 송전탑의 개수를 비교하여, 그 차이를 최소화하는 것이 목표입니다. 주어진 문제는 트리 구조로 연결된 송전탑 간의 전선을 하나씩 끊고, 각 전력망의 송전탑 개수를 계산하는 방식으로 해결할 수 있습니다. 이를 위해서는 전선이 끊어진 상태에서 두 전력망을 효율적으로 탐색하고, 그 차이를 구하는 방법이 필요합니다.

  • 그래프 생성: 먼저 송전탑 간의 연결 관계를 인접 리스트 형태로 그래프에 저장합니다. 인접 리스트는 각 송전탑(노드)에서 연결된 다른 송전탑으로 빠르게 접근할 수 있어, 그래프 탐색에 적합한 구조입니다. 이 과정에서 각 송전탑 번호와 인덱스를 일치시키기 위해 0번 인덱스를 비워두고, 1번부터 송전탑을 연결합니다.
  • 전선 끊기: 모든 전선을 하나씩 끊어보며, 두 전력망으로 나눕니다. 전선을 끊으면 두 전력망이 어떻게 분리되는지를 파악할 수 있으며, 인접 리스트에서 해당 전선 정보를 제거하여 끊긴 상태를 구현합니다. 이 과정은 반복적으로 전선을 하나씩 끊어가며 수행됩니다.
  • DFS 탐색: 전선을 끊은 후, DFS을 통해 한쪽 전력망의 송전탑 개수를 구합니다. DFS는 재귀적으로 노드를 방문하면서 연결된 모든 송전탑을 탐색하는 데 매우 유용한 방법입니다. 탐색한 노드는 별도의 배열로 기록하여 중복 탐색을 방지하며, 한쪽 전력망에 속한 송전탑들의 총 개수를 계산합니다.
  • 차이 계산: 한쪽 전력망의 송전탑 개수를 구한 후, 나머지 전력망의 송전탑 개수는 전체 송전탑 개수에서 이를 빼서 구합니다. 이렇게 구한 두 전력망의 송전탑 개수 차이의 절대값을 계산하여, 최소 차이를 찾아내는 것이 목표입니다.
  • 최소값 갱신: 각 전선을 끊어가며 계산된 송전탑 개수 차이를 비교하여, 가장 작은 차이를 갱신해 나갑니다. 매번 새로운 차이를 계산한 후, 현재까지의 최소값과 비교하여 더 작은 값을 저장합니다. 이를 통해 두 전력망의 송전탑 개수 차이가 가장 작은 경우를 찾아냅니다.
  • 전선 복구: 전선을 끊어 탐색이 완료된 후에는 끊었던 전선을 다시 복구하여 원래의 그래프 상태로 되돌립니다. 이렇게 해야 다른 전선을 끊을 때 이전 상태에 영향을 주지 않으며, 전선을 하나씩 반복적으로 끊어가며 탐색할 수 있습니다.
3. 송전탑 간 전선 연결을 통한 그래프 구축

먼저 전선으로 연결된 송전탑의 상태를 그래프로 표현합니다. 이를 위해 인접 리스트를 사용하여 송전탑 간의 연결 관계를 저장합니다. 각 송전탑은 해당 번호의 리스트에 자신과 연결된 다른 송전탑 번호를 저장하며, 양방향 연결을 고려하여 양쪽 송전탑 모두의 리스트에 서로의 번호를 추가합니다.

전체 송전탑의 개수는 n이지만, 송전탑 번호가 1번부터 시작하므로 그래프의 인덱스를 1번부터 맞추기 위해 0번 인덱스는 비워둡니다. 따라서 리스트의 크기를 n + 1로 초기화하여, 1번부터 n번까지의 송전탑을 대응할 수 있도록 설정합니다.

Solution.java
// 전체 송전탑 간 연결 상태를 저장하는 그래프
List<List<Integer>> graph = new ArrayList<>();        
for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());

// 송전탑들 간의 연결 상태를 그래프에 저장
for (int[] wire : wires) {
    int node1 = wire[0];
    int node2 = wire[1];
    graph.get(node1).add(node2);
    graph.get(node2).add(node1);
}
4. 전선을 임시로 끊어 두 전력망 분리

두 전력망으로 나뉜 송전탑의 개수를 비교하기 위해 전선을 임시로 끊습니다. 각 전선을 끊어 두 전력망을 분리한 후, 송전탑 개수 차이를 계산하여 최소 차이를 찾는 것이 목표입니다. 이를 위해 그래프에서 각 노드의 연결 관계를 찾아서 해당 연결을 임시로 제거합니다.

Solution.java
for (int[] wire : wires) {
    // 현재 처리 중인 전선의 두 송전탑 노드를 가져오기
    int node1 = wire[0];  // 첫 번째 송전탑 노드
    int node2 = wire[1];  // 두 번째 송전탑 노드
    
    // 두 송전탑 간의 연결을 임시로 끊음
    graph.get(node1).remove((Integer) node2);
    graph.get(node2).remove((Integer) node1);
    
    ...
}
5. 한쪽 전력망의 송전탑 개수 계산

전선을 끊은 후 한쪽 전력망에 속한 송전탑의 개수를 계산합니다. 전선을 끊은 한쪽 송전탑을 시작점으로 하여 해당 전력망에 포함된 모든 송전탑을 탐색하고 개수를 구합니다. 다른 전력망의 송전탑 개수는 전체 송전탑 개수에서 차감하여 구할 수 있습니다.

Solution.java
for (int[] wire : wires) {
    ...
    
    // 한 쪽 송전탑의 노드 개수 계산
    int count = dfs(graph, new boolean[n + 1], node1);
    
    ...
}

전선을 끊은 후, 한쪽 서브 트리의 송전탑 개수를 구하기 위해 DFS를 사용합니다. DFS는 재귀적으로 그래프를 탐색하며, 방문한 송전탑을 기록하고 송전탑 개수를 카운트합니다. 이를 통해 끊어진 전선으로 나뉜 서브 트리의 크기를 정확히 계산할 수 있습니다.

DFS 탐색 과정에서 중복 탐색을 방지하기 위해 별도의 배열을 사용합니다. 각 송전탑을 방문할 때 해당 노드를 배열에 기록하고, 이미 방문한 노드는 다시 탐색하지 않도록 하여 불필요한 반복을 막습니다. 이렇게 하면 효율적으로 송전탑 개수를 계산할 수 있으며, 서브 트리에 속한 송전탑의 정확한 개수를 빠르게 구할 수 있습니다.

Solution.java
private int dfs(List<List<Integer>> graph, boolean[] marked, int node) {
    // 현재 송전탑 방문 처리
    marked[node] = true;
    int count = 1;  // 현재 송전탑 카운트
    
    // 현재 송전탑과 연결된 다른 송전탑들 탐색
    for (int next : graph.get(node)) {
        // 이미 방문한 송전탑은 건너뜀
        if (!marked[next]) {
            // 방문하지 않은 송전탑에 대해 재귀적으로 탐색하고 개수를 누적
            count += dfs(graph, marked, next);
        }
    }
    // 연결된 모든 송전탑의 개수를 반환
    return count;
}
6. 두 전력망의 송전탑 개수 차이 계산 및 최소값 갱신

전선을 하나씩 끊을 때마다 한쪽 전력망의 송전탑 개수를 계산하고, 그에 따라 다른 전력망의 송전탑 개수는 전체에서 차감하여 구합니다. 두 전력망의 송전탑 개수 차이를 구한 후, 이 차이가 현재까지의 최소값보다 작으면 그 값을 업데이트하여 최소 차이를 트래킹합니다.

Solution.java
for (int[] wire : wires) {
    ...
    
    // 두 전력망의 송전탑 개수 차이를 계산하고 최소값 갱신
    int currentDiff = Math.abs((n - count) - count);
    minDiff = Math.min(currentDiff, minDiff);

    ...
}
7. 전선 복구 및 다음 전선 처리

전선을 끊어 두 전력망을 분리하고 그에 따른 송전탑 개수 차이를 계산한 후, 전선을 다시 원래 상태로 복구해야 합니다. 이렇게 전선을 복구하는 이유는, 다음 전선을 끊을 때 기존 그래프의 연결 상태를 유지하기 위해서입니다. 전선을 끊은 후 그 상태를 테스트한 후에는 원래 연결 상태로 돌아와야 다른 전선에 대한 동일한 작업을 수행할 수 있습니다.

이 과정은 모든 전선을 하나씩 끊고 복구하는 작업을 반복하며, 그때마다 두 전력망의 송전탑 개수 차이를 비교하게 됩니다.

Solution.java
for (int[] wire : wires) {
    ...
    
    // 끊었던 전선 복구: 다시 원래 상태로 복원하여 다음 전선 작업에 영향이 없도록 함
    graph.get(node1).add(node2);
    graph.get(node2).add(node1);
}
8. 최종 결과 반환

최종적으로 루프가 완료되면, 최소 차이를 나타내는 값이 저장되어 있으며, 이 값을 반환합니다. 이는 두 전력망 간의 송전탑 개수가 가장 비슷한 경우를 의미합니다.

Solution.java
// 결과 반환
return minDiff;

󰄉 Complexity

  • ⏳ TC: O(n^2)
  • 💾 SC: O(n)

전선을 하나씩 끊고 그 결과를 확인하는 과정에서 매번 DFS 탐색을 수행하므로, 시간 복잡도는 O(n^2)입니다. 그래프를 저장하는 데 필요한 공간은 송전탑의 개수에 비례하므로, 공간 복잡도는 O(n)입니다.

  • Algorithm
  • DFS