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

문제

---

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

풀이

---

전력망 네트워크를 2개로 분할하고, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추기 위해 각각의 배열 원소를 제외하고 BFS를 통해 나뉘어진 송전탑 개수를 카운트한다. 그리고 이중 절댓값이 가장 낮은 값을 return한다.

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

using namespace std;

int cnt;
int num_wire;
int connected;

void BFS(int start, vector<vector<int>> connect)
{
    int visit[101] = { 0 };
    queue<int> q;
    q.push(start);
    visit[start] = true;
    connected = 1;

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

        for (int i = 0; i < connect[x].size(); i++)
        {
            int y = connect[x][i];
            if (!visit[y]) 
            {
                q.push(y);
                visit[y] = true;
                connected++;
            }
        }
    }

    //bool istrue = false;

    
}

int solution(int n, vector<vector<int>> wires)
{
    int answer = 20000;
    num_wire = n;

    for (int i = 0; i < wires.size(); i++)
    {
        vector<vector<int>> connect(101);
        cnt = 0;

        for (int j = 0; j < wires.size(); j++)
        {
            if (i == j)
            {
                continue;
            }

            else
            {
                connect[wires[j][0]].push_back(wires[j][1]);
                connect[wires[j][1]].push_back(wires[j][0]);
            }
        }

        bool isOneSeparate = false;

        for (int j = 1; j <= wires.size(); j++)
        {
            if (connect[j].size() == 0)
            {
                isOneSeparate = true;
                break;
            }
        }

        int result = 0;

        if (!isOneSeparate)
        {
            //1부터 시작해서 3으로 이동 3에서 2로 이동 2에서 3으로 밖에 경로가 없을 때 재귀 종료
            // BFS에 갔다가 원래 숫자로 되돌아오면 break;
            BFS(1, connect);

            result = abs(n - connected - connected);
        }

        else
        {
            result = n - 2;
        }

        if (answer > result)
        {
            answer = result;
        }
    }


    return answer;
}