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

💡 문제
전력망을 둘로 나누기 (https://school.programmers.co.kr/learn/courses/30/lessons/86971)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

---

🤓 문제 풀이

주어진 문제는 송전탑 네트워크에서 하나의 전선을 끊어 두 개의 전력망으로 나누었을 때, 각 전력망이 가지고 있는 송전탑 개수의 차이를 최소화하는 것입니다. 이를 위해, 각 전선을 하나씩 끊어보고, 끊어진 두 개의 전력망의 송전탑 개수를 계산한 후, 차이를 비교하여 최소값을 찾아야한다.

송전탑의 개수가 최대한 비슷하도록 두 전력망으로 나누는 것입니다. 이는 그래프에서 하나의 엣지를 끊고 연결된 두 컴포넌트의 크기를 계산하는 문제로 접근할 수 있습니다.

---

 

입출력 예 1)

- 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.

- 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

 

입출력 예 2

- 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

 

입출력 예3 

- 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

---

접근방법

• 문제의 요구사항은 송전탑의 개수가 최대한 비슷하도록 두 전력망으로 나누는 것입니다. 이는 그래프에서 하나의 엣지를 끊고 연결된 두 네트워크의 크기를 계산하는 문제로 유추할 수 있습니다.
• 제한사항에 따라, n은 최대 100이므로, 모든 전선을 하나씩 끊어보는 완전탐색 방법이 적합합니다.
• 전선을 끊었을 때 연결된 네 트크트의크 기를를계계하기산 BFS 또는 DFS 탐색을 사용합니다.

---

문제 풀이 과정

그래프 표현

• 주어진 송전탑과 전선 정보를 그래프의 노드와 엣지로 모델링합니다. 각 송전탑은 노드로, 전선은 두 노드를 연결하는 엣지로 표현합니다.

전선 끊기 (연결 끊기 및 탐색)

• 각 전선을 하나씩 끊어서 그래프를 두 개의 컴포넌트로 나눕니다. 이때, 끊어진 전선의 두 노드가 속한 두 개의 컴포넌트를 찾습니다.
• 각 전선을 하나씩 끊어보고, 끊어진 두 네트워크를 BFS를 사용해 탐색하여 각 컴포넌트의 크기를 계산.

차이 계산

• 제한사항에 따라, n은 최대 100이므로, 모든 전선을 하나씩 끊어보는 완전탐색 방법이 적합합니다.
• 각 전선을 끊었을 때, 두 컴포넌트의 크기를 계산합니다. BFS 또는 DFS를 사용하여 한쪽 컴포넌트의 노드 개수를 세고, 전체 노드 개수에서 이를 빼면 다른 컴포넌트의 크기를 알 수 있습니다.
• 하나의 전선을 끊었을 때, 두 개의 네트워크로 나뉩니다. 이때 각 네트워크의 송전탑 개수를 계산해야 합니다.
• 전선을 끊었을 때 연결된 컴포넌트의 크기를 계산하기 위해 BFS 또는 DFS 탐색을 사용합니다.
• 이를 위해 BFS 또는 DFS 탐색을 사용하여 끊어진 네트워크의 송전탑 개수를 구합니다.
• 두 네트워크의 송전탑 개수의 차이를 계산하고, 이를 반복하여 최소값을 찾습니다.
• 두 전력망의 송전탑 개수 차이의 최소값을 반환.

---

구현코드

import java.util.*;

class Solution {
    // 인접 리스트를 사용하여 그래프를 표현합니다.
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE; // 최종적으로 최소 차이를 저장할 변수
        List<Integer>[] graph = new ArrayList[n + 1];
        
        // 그래프 초기화
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 주어진 전선 정보로 그래프를 구성합니다.
        for (int[] wire : wires) {
            graph[wire[0]].add(wire[1]);
            graph[wire[1]].add(wire[0]);
        }
        
        // 각 전선을 하나씩 끊어봅니다.
        for (int[] wire : wires) {
            // 끊는 전선
            int v1 = wire[0];
            int v2 = wire[1];
            
            // 연결 끊기
            graph[v1].remove(Integer.valueOf(v2));
            graph[v2].remove(Integer.valueOf(v1));
            
            // 두 전력망으로 나누어진 각 송전탑의 개수를 계산
            int count1 = bfs(v1, graph, n);
            int count2 = n - count1;
            
            // 두 전력망의 송전탑 개수 차이를 계산
            answer = Math.min(answer, Math.abs(count1 - count2));
            
            // 연결 복구
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        
        return answer;
    }
    
    // BFS를 사용하여 연결된 송전탑의 개수를 세는 함수
    private int bfs(int start, List<Integer>[] graph, int n) {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        int count = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        
        return count;
    }
}

---

📚 풀이 보완

코드 설명

1. 그래프 초기화 및 구성:
   • 먼저, 주어진 송전탑 개수와 전선 정보를 사용하여 그래프를 인접 리스트 형태로 초기화합니다. 인접 리스트를 사용하면 노드 간의 연결 정보를 효율적으로 저장하고 탐색할 수 있습니다.

// 인접 리스트를 사용하여 그래프를 표현합니다.
List<Integer>[] graph = new ArrayList[n + 1];

// 그래프 초기화
for (int i = 1; i <= n; i++) {
    graph[i] = new ArrayList<>();
}

// 주어진 전선 정보로 그래프를 구성합니다.
for (int[] wire : wires) {
    graph[wire[0]].add(wire[1]);
    graph[wire[1]].add(wire[0]);
}

 

2. 전선 끊기 및 탐색:

• 각 전선을 하나씩 끊고, 끊어진 그래프에서 BFS 탐색을 수행하여 컴포넌트의 크기를 계산

// 각 전선을 하나씩 끊어봅니다.
for (int[] wire : wires) {
    // 끊는 전선
    int v1 = wire[0];
    int v2 = wire[1];

    // 연결 끊기
    graph[v1].remove(Integer.valueOf(v2));
    graph[v2].remove(Integer.valueOf(v1));

    // 두 전력망으로 나누어진 각 송전탑의 개수를 계산
    int count1 = bfs(v1, graph, n);
    int count2 = n - count1;

    // 두 전력망의 송전탑 개수 차이를 계산
    answer = Math.min(answer, Math.abs(count1 - count2));

    // 연결 복구
    graph[v1].add(v2);
    graph[v2].add(v1);
}

 

3. BFS 탐색:

• BFS 탐색을 사용하여 연결된 노드의 개수를 세어 한쪽 컴포넌트의 크기를 계산합

// BFS를 사용하여 연결된 송전탑의 개수를 세는 함수
private int bfs(int start, List<Integer>[] graph, int n) {
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited[start] = true;
    int count = 0;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        count++;
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }

    return count;
}

---

📍 Plus+

시간 복잡도 분석

• 전선을 하나씩 끊는 작업은 총 n−1번 수행됩니다. 각 전선을 끊을 때마다, 송전탑 네트워크를 두 개의 컴포넌트로 나누고 각 컴포넌트의 크기를 계산하는데 BFS 탐색을 사용합니다.
• 전선을 끊는 작업은 O(n-1)이고, 각 전선을 끊을 때 BFS 탐색은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n * n) = O(n^2)입니다.
• BFS 탐색은 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다.
• 따라서, 전선을 하나씩 끊어보고 BFS 탐색을 수행하는 전체 작업의 시간 복잡도는 O((n−1)×n)=O(n2)입니다.
• O((n−1)×n)=O(n2)O((n-1) \times n) = O(n^2)

공간 복잡도

• 그래프를 인접 리스트로 표현하므로, 인접 리스트의 공간 복잡도는 O(n+m)입니다. 여기서 m은 엣지의 수인데, 이 문제에서 m=n−1이므로 인접 리스트의 공간 복잡도는 O(n+(n−1))=O(n)입니다.mmO(n+(n−1))=O(n)O(n + (n-1)) = O(n)
• 그래프를 표현하기 위한 인접 리스트는 O(n + m) 공간을 사용합니다. 여기서 m은 엣지의 수로, m = n-1이므로 O(n)입니다. BFS 탐색을 위한 추가 공간도 O(n)입니다.
• BFS 탐색을 위한 추가 공간으로 큐와 방문 배열이 필요합니다. 큐의 최대 크기는 n이며, 방문 배열의 크기도 n이므로 BFS 탐색을 위한 공간 복잡도는 O(n)입니다.

요약

• 시간 복잡도: O(n2)
  • n−1n-1n−1개의 전선을 하나씩 끊고, 각 경우에 대해 BFS 탐색을 수행하는 데 O(n)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(n2)입니다.
• 공간 복잡도: O(n)
  • 그래프를 인접 리스트로 표현하는 데 O(n)의 공간이 필요하며, BFS 탐색을 위한 추가 공간도 O(n)이므로 전체 공간 복잡도는 O(n)입니다.