전력망을 둘로 나누기(25분)

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

구현 아이디어 3분 구현 22분

풀이

#include <string>
#include <vector>

using namespace std;

vector<int> graph[101];
int min_sub = 2147000000;
int check[101];

int DFS(int parent)
{
    check[parent] = 1;
    int num_child = 1;
    if(graph[parent].size() == 0) return num_child;
    for(int i = 0; i < graph[parent].size(); ++i)
        if(check[graph[parent][i]] == 0) num_child += DFS(graph[parent][i]);
    
    return num_child;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    
    // 정점 개수.
    int N = wires.size() + 1;
    for(int i = 0; i < N - 1; ++i)
    {
        wires[i];   // 이 간선은 추가하지 않을 것임.
        int parent = -1;
        for(int j = 0; j < N - 1; ++j)
        {
            if(i == j)
            {
                parent = wires[i][0];
                continue;
            }
            graph[wires[j][0]].push_back(wires[j][1]);
            graph[wires[j][1]].push_back(wires[j][0]);
        }
        
        // 연결 끝. DFS 탐색.
        int num_nodes = DFS(parent);
        int sub = N - num_nodes;
        
        sub = abs(num_nodes - sub);
        
        if(min_sub > sub) min_sub = sub;
        
        // 디버깅.    
        //if(sub == 0)
            //printf("parent: %d, num_nodes: %d N: %d\n", parent, num_nodes, N);
        
        for(int j = 1; j <= N; ++j)
        {
            graph[j].clear();
            check[j] = 0;
        }
    }
    
    return answer = min_sub;
}