[c++/프로그래머스] 전력망을 둘로 나누기

문제 링크

전력망을 둘로 나누기

풀이

BFS와 완전탐색으로 푸는 문제

1. wires를 하나씩 지워가며(전선을 끊으면서) 각각의 송전탑 개수를 구한다.
2. 송전탑 개수를 구하는 것은 BFS를 활용하였다.
   2-1. queue를 사용하여 BFS를 구현하고 cnt는 그 전력망의 송전탑 개수가 들어간다.
   2-2. cnt2는 다른쪽 전력망의 송전탑 개수인데, 인덱스 1부터 시작했기 때문에 v.size()-1-cnt가 된다.
3. cnt2와 cnt1의 차이가 최소인 것을 갱신한다.

코드

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

using namespace std;

int gap(vector<vector<int>> v)
{
    vector<int> visit(v.size());
    queue<int> q;
    
    q.push(1);
    int cnt = 0;
    
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if(visit[cur]==1) continue;
        visit[cur]=1;
        cnt++; // 이어진 송전탑 개수
        for(int i=0;i<v[cur].size();i++)
        {
            q.push(v[cur][i]);
        }
    }
    int cnt2 = v.size()-1-cnt;
    return abs(cnt2-cnt);
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 1000;
    
    for(int i=0;i<wires.size();i++)
    {
        vector<vector<int>> v(n+1);
        for(int j=0;j<wires.size();j++)
        {
            if(i==j) continue;
            int stt = wires[j][0];
            int end = wires[j][1];
            v[stt].push_back(end);
            v[end].push_back(stt);
        }
        answer = min(answer, gap(v));
        v.clear();
    }
    return answer;
}