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

문제

접근 방법

이차원 bool 배열로 이미 잘라 본 전선인지 확인하며 BFS하면 된다고 생각했다.
왔다 간 곳인지 확인할 용도의 bool 배열을 선언하고 자른 전선이 위치한 2곳을 true로 선언하면 BFS할 때 분리된 네트워크 건너편으로 못 갈 것이라고 생각했다. (건너편으로 갈 길목은 이미 true이기에 못간다) 그렇다면 각자의 네트워크에서 탐색하게 될 것이고 탐색한 값을 구하여 격차를 구하면 된다고 생각했다.

코드

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

using namespace std;

int solution(int n, vector<vector<int>> wires)
{
    bool visit[101];
    bool check[101][101];
    vector<vector<int>> wV;
    for (int i = 0; i < 101; i++)
    {
        wV.push_back(vector<int>());
    }
    int answer = 101;
    queue<int> bfs;
    for (vector<int> wire : wires)
    {
        wV[wire[0]].push_back(wire[1]);
        wV[wire[1]].push_back(wire[0]);
    }

    for (int i = 1; i <= wV.size(); ++i)
    {
        for (int j = 0; j < wV[i].size(); ++j)
        {
            if (check[i][wV[i][j]]) // 이미 분리해봤다면 넘김
                continue;
            check[i][wV[i][j]] = true;
            int record = 0;
            visit[i] = true;
            visit[wV[i][j]] = true;
            bfs.push(wV[i][j]);
            while (!bfs.empty()) // 더하는 부분
            {
                int curPos = bfs.front();
                visit[curPos] = true;
                bfs.pop();
                ++record;
                for (int k = 0; k < wV[curPos].size(); ++k)
                {
                    if (!visit[wV[curPos][k]])
                    {
                        bfs.push(wV[curPos][k]);
                    }
                }
            }
            bfs.push(i);
            while (!bfs.empty()) // 빼는 부분
            {
                int curPos = bfs.front();
                visit[curPos] = true;
                bfs.pop();
                --record;
                for (int k = 0; k < wV[curPos].size(); ++k)
                {
                    if (!visit[wV[curPos][k]])
                    {
                        bfs.push(wV[curPos][k]);
                    }
                }
            }
            if (abs(record) < answer)
                answer = abs(record);
            memset(visit, false, sizeof(visit));
        }
    }
    return answer;
}

풀이

2차원 벡터를 만들어주고 연결된 송전탑을 서로 추가해주면 된다. 이후 송전탑이 될 수 있는 만큼, 그 송전탑에 연결된 송전탑만큼 반복문을 돌려준다.
반복문안에선 두 네트워크에 송전탑 격차를 계산해준다. while문이 중복됐는데 함수로 해결할 수 있지만 전역변수를 선언하기 싫고 함수 호출 안 하려고 안 했다.
i는 연결된 송전탑보다 작기에 2차원 bool 배열 check에서도 i를 앞세워서 한 번만 확인해주면 된다.