Level 2. 전력망을 둘로 나누기

Level 2. 전력망을 둘로 나누기

 

 

2차원 vector를 활용한 인접 리스트로 그래프를 만들었고, 각 연결을 끊고 끊은 두 지점부터 DFS를 수행해 차이를 계산한 최솟값을 구하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int rDFS(vector<vector<bool>>& tree, int vertex)
{
    int nConnected = 1;

    for (int j = 1; j < tree.size(); ++j)
    {
        if (tree[vertex][j])
        {
            tree[vertex][j] = tree[j][vertex] = false,
            nConnected += rDFS(tree, j);
        }
    }

    return nConnected;
}

int calculate(vector<vector<bool>> tree, vector<int>& discon)
{
    tree[discon[0]][discon[1]] = tree[discon[1]][discon[0]] = false;

    return abs(rDFS(tree, discon[0]) - rDFS(tree, discon[1]));
}

int solution(int n, vector<vector<int>> wires)
{
    int answer = 100;
    vector<vector<bool>> tree(n + 1, vector<bool>(n + 1, false));

    for (auto& wire : wires)
        tree[wire[0]][wire[1]] = tree[wire[1]][wire[0]] = true;

    for (auto& wire : wires)
        answer = min(answer, calculate(tree, wire));

    return answer;
}