[프로그래머스 lv2] 전력망을 둘로 나누기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

트리는 정점이 V, 간선이 V-1개 이고 사이클이 없는 그래프이다.

주어진 wires 중에 한개를 골라 자르면 해당 트리는 두개의 트리로 나누어지게 된다.

 

wires를 순회하면서 각 와이어를 끊고, 와이어에 연결된 정점 중 하나를 시작지점으로 트리를 탐색하자.

첫번째 트리를 구성하는 노드 개수가 cnt개 일 때, 나머지 트리의 노드 개수는 n-cnt가 된다. 

두 트리의 노드 차 cnt-(n-cnt)의 최솟값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

void setGraph(vector<vector<int>>& graph, const vector<vector<int>>& wires, int idx) {
    
    for (int i=0; i<wires.size(); i++) {
        if (idx == i) continue;
        int u = wires[i][0];
        int v = wires[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

int cntNodes(const vector<vector<int>>& graph, int start) {
    
    vector<bool> check(graph.size(), false);
    
    int cnt = 0;
    queue<int> q;
    q.push(start);
    check[start] = true;
    
    while (!q.empty()) {
        
        int cur = q.front();
        q.pop();
        cnt++;
        
        for (auto x : graph[cur]) {
            if (check[x]) continue;
            q.push(x);
            check[x] = true;
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    
    int mn = n;
    for (int i=0; i<wires.size(); i++) {
        vector<vector<int>> graph(n+1, vector<int>(0));
        setGraph(graph, wires, i);
        int cnt = cntNodes(graph, wires[i][0]);
        mn = min(mn, abs(cnt-(n-cnt)));
    }
    return mn;
}