프로그래머스 - 전력망을 둘로 나누기

 코딩테스트 고득점 Kit 완전탐색 Level 2 전력망을 둘로 나누기 문제이다. 나는 처음에 이 문제를 유니온 파인드를 이용해서 풀려고 했지만 구현이 쉽지 않았다. 입력 n 이 100으로 아주 작고, 트리로 주어지므로 시간 복잡도가 100 * 100 * 100 정도로 아주 작다. 따라서 이 문제는 완전 탐색, dfs를 이용해서 풀었다. dfs가 끝날 때마다 temp++를 실행함으로써 dfs가 최종 종료했을 때 몇개의 노드가 연결되어있는지 알수 있도록 구현했다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int ans = INT32_MAX;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> result;
int temp;

void dfs(int n, int start)
{
    visited[start] = true;
    
    for (int i = 0; i < adj[start].size(); i++)
    {
        int next = adj[start][i];
        
        if (!visited[next])
        {
            dfs(n, next);
        }
    }
    
    temp++;
}

void func(int n, vector<vector<int>>& wires)
{
    for (int i = 0; i < wires.size(); i++)
    {
        adj = vector<vector<int>>(n + 1);
        visited = vector<bool>(n + 1, false);
        result = vector<int>();
    
        for (int j = 0; j < wires.size(); j++)
        {
            if (i == j)
            {
                continue;
            }
            
            int a = wires[j][0];
            int b = wires[j][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
            {
                temp = 0;
                dfs(n, i);
                result.push_back(temp);
            }
        }
        
        ans = min(ans, abs(result[0] - result[1]));
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    
    func(n, wires);
    
    answer = ans;
    
    return answer;
}