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

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

프로그래머스

 이번 문제는 전력망들의 연결 상태가 주어졌을 때, 딱 하나의 연결만을 끊어서 나뉘는 두 집합의 노드 개수의 차이의 최대값을 구하는 문제이다. 이 문제의 카테고리가 완전탐색이라는 점에서 알 수 있듯, 모든 연결을 한 번 씩 끊어본 후, 두 구역의 노드 개수를 구하면 되는 간단한 문제라 할 수 있다. 그리고 노드의 개수는 BFS를 이용하여 구할 수 있다. 이것들을 고려하여 구상한 해결 절차는 다음과 같다.

1. 첫 wire부터 마지막 wire까지 하나씩 끊을 wire를 반복문으로 정한다.
2. 1번에서 고른 wire를 제외한 후의 연결 상태를 저장한다.
3. 2번에서 알아낸 연결 상태를 이용해 각 노드별로 BFS를 수행하여 구역별 노드의 개수를 구한다.
4. 노드 개수의 차이의 절댓값을 비교하여 답을 구한다.

 

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

using namespace std;

#define MAX 101

int nodeNum;
bool visited[MAX];
vector<int> links[MAX];
vector<vector<int>> allWires;

int Search(int node)
{
    queue<int> q;
    q.push(node);
    visited[node] = true;

    int count = 1;

    while(!q.empty())
    {
        int curNode = q.front();
        q.pop();

        ++count;

        for (int i = 0; i < links[curNode].size(); ++i)
        {
            int nxtNode = links[curNode][i];

            if (visited[nxtNode] == false)
            {
                visited[nxtNode] = true;
                q.push(nxtNode);
            }   
        }
    }

    return count;
}

int Check(int disconnected)
{
    for (int node = 1; node <= nodeNum; ++node)
    {
        links[node].clear();
        visited[node] = false;
    }

    for (int wire = 0; wire < allWires.size(); ++wire)
    {
        if (wire == disconnected)
            continue;

        int nodeA = allWires[wire][0];
        int nodeB = allWires[wire][1];

        links[nodeA].push_back(nodeB);
        links[nodeB].push_back(nodeA);
    }

    vector<int> counts;

    for (int node = 1; node <= nodeNum; ++node)
    {

        if (visited[node] == false)
            counts.push_back(Search(node));
    }

    return abs(counts[0] - counts[1]);
}

int solution(int n, vector<vector<int>> wires) 
{
    nodeNum = n;
    int answer = MAX + MAX;
    allWires = wires;

    for (int disconnected = 0; disconnected < wires.size(); ++disconnected)
    {        
        int diff = Check(disconnected);

        if (answer > diff)
            answer = diff;
    }

    return answer;
}