[프로그래머스/JAVA] 고득점Kit > 완전탐색 > 전력망을 둘로 나누기 (by 다알쥐AI)

고득점Kit > 완전탐색 > 전력망을 둘로 나누기

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

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

 

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

---

제한사항

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

---

입출력 예

 

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
• 
• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

입출력 예 #3

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

  

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

---

[간단설명]

전력망을 둘로 나눠서 두 개의 송전탑의 차이가 가장 작은 값을 리턴 

 

[접근방법]

1. 두 노드간 양방향 그래프를 구성한다.

2. 송전탑의 길이를 구하는 BFS 함수를 만든다.

3. 1번 전력망부터 n번까지 자식 노드 연결을 끊어가면서 송전탑의 길이를 구한다.

4. 두 송전탑의 차를 구한다.

5. 가장 작은 값을 리턴한다.

 

[주의사항]

1. 그래프는 양방향으로 구현한다.

    -> 단방향이면 송전탑 길이를 구하기 어렵다.

2. 부모 노드의 자식 노드는 1개가 아니라 여러 개이므로, 자식노드 전부를 탐색해야 한다.

3. 전력망을 끊는 방법을 고민해본다

    -> 여기에서는 visited 로 방문체크하여 연결을 끊었다.

 

[소스공개]

import java.util.*;
class Solution {
    // Node 클래스
    class Node{
        int num;         // 망번호
        List<Node> edge; // 자식노드 리스트
        boolean visited; // 방문여부
        
        // 생성자 
        Node(int num){
            this.num = num;
            this.edge = new LinkedList<>();
        }
        // 자식노드 추가 
        void add(Node node){
            edge.add(node);
        }
    }
    public int solution(int n, int[][] wires) {
        // Node 리스트 
        List<Node> list = new ArrayList<>();
        
        // Node 리스트 만들기
        // (망번호 1번 ~ n번) 0번째는 비워둠 
        for(int i=0; i<n+1; i++){
            Node node = new Node(i);
            list.add(node);
        }
        
        // 전력망 연결(양방향 그래프 구성)
        // ex) [1,3]
        // 1번 노드에 3번 자식노드 추가
        // 3번 노드에 1번 자식노드 추가
        for(int[] w : wires){
            Node node1 = list.get(w[0]);
            Node node2 = list.get(w[1]);
            node1.add(node2);
            node2.add(node1);
        }
        
        // 정답 최소값 => n이 100이하
        int min = 100;
        // 전력망 1번부터 n번까지 완전탐색 
        for(int i=1;i<n+1;i++){
            // i번째 망 꺼냄
            Node first = list.get(i);
            // i번째 망 자식노드 순회(자식이 여러개 일수 있다)
            for(Node second : first.edge){
                // cnt1 = i번째 망 순회(first)
                // cnt2 = 자식노드 순회(second)
                int cnt1 = bfs(first, second, list, n);
                int cnt2 = bfs(second, first, list, n); 
                
                // 최소값 갱신
                min = Math.min(min,Math.abs(cnt1-cnt2));
                
            }
        }
        
        //int answer = -1;
        return min;
    }
    
    // BFS 함수 
    private int bfs(Node first, Node second, List<Node> list, int n){
        
        // 방문 초기화
        for(int i=1;i<n+1;i++){
            list.get(i).visited=false;
        }
        
        // 망 연결끊기(i 번째 망 <-> 자식노드) 
        // 여기에서는 방문체크로 망을 끊었다고 가정한다
        // 방문체크를 하면 두 연결고리가 끊어져서 더 이상 탐색하지 않는다
        first.visited = true;
        second.visited = true;
        
        // BFS용 큐 
        // first 노드 넣어줌 
        Queue<Node> que = new LinkedList<>();
        que.offer(first);
        
        // 송전탑 길이 
        int cnt=0;
        while(!que.isEmpty()){
            // 큐를 하나 꺼낸다
            Node now = que.poll();
            // 큐에 연결된 자식 노드만큼 반복
            for(Node next : now.edge){
                if(next.visited) continue;
                next.visited = true;
                que.offer(list.get(next.num));
            }
            // 송전탑 길이 증가
            cnt++;
        }
        // cnt 리턴
        return cnt;
    }
}

 

[실행결과]