[프로그래머스] (Java) 전력망을 둘로 나누기 (완전탐색)

 

📑 1. 문제설명

 

입출력 예 설명

입출력 예 #1
다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.

 

4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

 

입출력 예 #2
다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

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

 

입출력 예 #3

다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

 

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

---

💡 2. 접근방식

이 문제에서 중요한 점은 전력망의 구조가 하나의 트리라는 것이다. 전선을 하나 끊었을 때 3개나 4개가 아닌 반드시 두 개가 된다. 분할된 전력망에서 송전탑 개수를 구한다음 서로의 차이를 계산하는 것보다 어차피 두 개로 분할 되는 것이기 때문에 `전체 송전탑의 개수 - 한 쪽의 송전탑 개수`를 해 줘도 된다.

 

트리 탐색을 해 주면 되는데 이 문제에서는 최적이나 최소값 구하는게 아니기 때문에 `깊이 우선 탐색(DFS)`을 사용하면 된다. 전체 전력망에 대해 깊이 우선 탐색을 하면서 자식 노드의 수를 계산해서 

| (전체 노드 - 자식 트리의 노드 수) - (자식 트리의 노드 수) |

 

의 절댓값이 가장 작은 것을 찾으면 된다. 

---

⭐ 3. 코드

import java.util.*;

class Solution {
    
    // 방문한 노드인지 체크, false로 초기화
    private static boolean[] visited;
    // 전선 연결 정보 저장할 인접 리스트
    private static ArrayList<Integer>[] adjList;
    // 송전탑 개수, 반환할 값
    private static int N, answer;
    
    public int solution(int n, int[][] wires) {
        N = n;
        // 네트워크가 단절되었을 때, 두 부분으로 나뉘는 송전탑 개수 차이의 최대값은 n−1
        answer = n - 1;
        
        // 1. 전선 연결 정보 저장할 인접 리스트 초기화
        adjList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        // 2. 전선 연결 정보를 연결 리스트에 저장(양방향)
        for (int[] wire : wires) {
            adjList[wire[0]].add(wire[1]);
            adjList[wire[1]].add(wire[0]);
        }
        
        visited = new boolean[n + 1];
        // 3. 깊이 우선 탐색 시작
        dfs(1);
        return answer;
    }
    
    private static int dfs(int now) {
        visited[now] = true;
        // 4. 자식 노드의 수를 저장하고 반환할 변수 sum
        int sum = 0;
        
        // 5. 연결된 모든 전선을 확인
        for (int next : adjList[now]) {
            if (!visited[next]) {
                // 6. (전체 노드 - 자식트리의 노드 수) - (자식트리의 노드 수)
                // 의 절대값이 가장 작은 값 구하기
                int cnt = dfs(next);
                answer = Math.min(answer, Math.abs(N - cnt * 2));
                // 7. 자식 노드의 수 더함
                sum += cnt;
            }
        }
        // 9. 전체 자식 노드의 수에 1(현재 now 노드)을 더해서 반환
        return sum + 1;
    }
}

 

1. 전선의 연결 정보 저장할 인접리스트 초기화

송전탑 번호가 0 아니구 1번부터 시작하니까 ArrayList 배열의 크기는 송전탑의 수 + 1

 

2. 전선 연결 정보를 인접 리스트에 저장

연결만 되어 있다면 탐색을 할 수 있도록 양방향으로 구현

for (int[] wire : wires) {
    adjList[wire[0]].add(wire[1]);
    adjList[wire[1]].add(wire[0]);
}

 

이렇게 해 주면 만약 wires가 [[1,3], [2,3], [3,4], [4,5]]일 때

 

adjList[1] = [3]

adjList[3] = [1]

 

adjList[2] = [3]

adjList[3] = [1, 2]

 

adjList[3] = [3, 4]

adjList[4] = [3]

 

adjList[4] = [3, 5]

adjList[5] = [4]

 

이렇게 하면 양쪽 송전탑 모두 다른 송전탑과 연결되어 있다는 정보를 저장할 수 있다.

 

 

3. 1번 송전탑부터 깊이 우선 탐색시작, 어떤 정점부터 탐색을 시작해도 동일한 값이 나온다

 

4. 자신의 자식 트리의 노드와 자신을 포함한 전체 노드의 수를 반환할 변수 sum 선언

 

5. 현재 노드(송전탐)에서 연결된 모든 전선 확인

dfs의 매개변수 now는 현재 방문 중인 노드(송전탑)로 코드에서 dfs 함수가 호출될 때마다, now는 그때그때 방문하고 있는 노드이다. 이 값을 통해서 깊이 우선 탐색(DFS)을 해 준다.

 

6. | (전체 노드 - 자식 트리의 노드 수) - (자식 트리의 노드 수) | 절대값 계산해서 최솟값을 answer에 저장

 

예를 들어, 송전탑의 총 개수가 6개이고
이걸 둘로 나눈 A부분의 자식 트리의 노드 수가 3개라면
나머지 송전탑(B)의 개수는 6 - 3 = 3개이다. 

B의 크기 - A의 크기에 절대값 씌우면 3 - 3 = 0

이 값이 A부분과 B 부분의 송전탑 개수의 차이이고, 현재 answer에 담긴 값과 현재 계산해 준 값을 비교 해서 더 작은 값으로 answer을 업데이트 한다. 

 

7. 자식 트리의 노드 수를 sum에 더함

 

8. 자신의 전체 자식 트리의 노드 수 + 1해서 자기 자신을 포함한 하위 트리의 모든 노드 수 반환

 

---

👉🏻 4. 같은 유형 문제