(c++) 프로그래머스 "전력망을 둘로 나누기"

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

코딩테스트 연습 - 전력망을 둘로 나누기

---

#include <string>
#include <vector>

using namespace std;
vector<int> m[200];

int bfs(int togo, int now, int count) {
    for (int i = 0; i < m[now].size(); i++) {
        if (m[now][i] != togo) {
            count = bfs(now, m[now][i], count+1);
        }
    }
    return count;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 2000;
    for (auto w : wires) {
        m[w[0]].push_back(w[1]);
        m[w[1]].push_back(w[0]);
    }
    for (auto w : wires) {
        int sum = bfs(w[0], w[1], 1);
        int comp = n - (2 * sum);
        answer = min(answer, abs(comp));
    }
    return answer;
}