[Programmers] 전력망을 둘로 나누기

그래프의 한 간선을 잘라서 생기는 두 집합의 노드의 수의 차이를 구하는 문제이다.

문제풀이 전략
그래프가 하나의 트리로만 구성되어 있으므로 모두 연결되어 있다는 것을 알 수 있다.

또한 트리이므로 사이클 역시 존재하지 않는다.

따라서 한 간선씩 그래프에서 지운 후 bfs나 dfs를 통해 노드의 수의 차이를 구하고 그 중 최솟값을 구하면 된다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    
    int m = n;
    for(int i=0;i<wires.size();i++){
        vector<int> v[n];
        for(int j=0;j<wires.size();j++){
            if(j == i)
                continue;
            int s = wires[j][0] - 1;
            int e = wires[j][1] - 1;
            v[s].push_back(e);
            v[e].push_back(s);
        }
        vector<int> visited(n);
        visited[0] = 1;
        queue<int> q;
        q.push(0);
        int cnt = 1;
        while(!q.empty()){
            int f = q.front();
            q.pop();
            for(int k=0;k<v[f].size();k++){
                if(visited[v[f][k]] == 1)
                    continue;
                visited[v[f][k]] = 1;
                q.push(v[f][k]);
                cnt++;
            }
        }
        m = min(abs(n-cnt-cnt),m);
    }
    answer = m;
    return answer;
}

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