문제 86971. 전력망을 둘로 나누기

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

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

입력

• 송전탑의 개수 n, 그리고 전선 정보 wires

입력 제한

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

입력 예제

// input
9                                                    // n
[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]    // wires

// ans
3

 

풀이 방식

전력망을 둘로 나눴을 때 나눠진 전력망의 노드 개수를 최대한 비슷하게 하려면 나눠진 각 전력망에 존재하는 노드 개수들을 알아야한다. 각 전력망에 존재하는 노드를 알기 위해서 본인은 각 노드가 가지는 하위 노드들의 개수를 저장하였다. 그리고 (전체 노드의 수 - 해당 노드가 가지는 하위 노드의 수)를 하여 이 값이 최소값이 되는 값을 구하는 방식으로 노드(송전탑)의 개수가 최소가 되는 개수를 찾아내었다. 

 

각 노드가 가지는 하위 노드들의 개수를 구한 방법

특정 노드가 가지는 하위 노드들의 개수를 구하는 방법은 완전 탐색을 통한 순회로 구할 수 있다. 순회면 무엇이든 사용해도 되기 때문에 dfs, bfs등을 활용할 수 있는데, 재귀적으로 노드의 개수를 구하고 싶었기에 본인은 dfs를 사용하였다. 

정답 코드 

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> tree;
vector<bool> visited;
vector<int> child_n;

int dfs(int idx){
    
    child_n[idx] = 1;
    
    for(int adj : tree[idx]){
        if(!visited[adj]){
            visited[adj] = true;
            child_n[idx] += dfs(adj);
        }
        
    }
    
    return child_n[idx];
}

int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    tree.resize(n+1);
    child_n.resize(n+1);
    visited.resize(n+1);
    
    for(vector<int> v1 : wires){
        tree[v1[0]].push_back(v1[1]);
        tree[v1[1]].push_back(v1[0]);
    }
    
    visited[1] = true;
    dfs(1);
    
    for(int i = 2; i <= n; i++){
        child_n[i] = abs(child_n[i] - abs(child_n[i] - child_n[1]));
    }
      
    answer = *min_element(child_n.begin()+2, child_n.end());
    
    return answer;
}