프로그래머스 Level 2 전력망나누기

전력망나누기 (프로그래머스 Level 2)

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

dfs를 통해 그래프 탐색이 필요한 문제이다
주어진 edge를 통하여 그래프의 인접 리스트를 만들고
각 인접 리스트를 dfs를 통해 탐색하여, 해당 노드를 루트로
삼았을 때, 셀 수 있는 노드의 개수를 구한다

이후, 해당 노드를 기준으로 절댓값 : (전체 노드의 수 - 현재 서브트리의 노드 수)
를 비교함으로서 ‘해당 노드가 포함된 그래프’와 그것이 아닌 그래프의
노드 수의 차이를 구할 수 있다

Code

#include <string>
#include <vector>
#include<math.h>
#include<limits.h>

using namespace std;

vector<int> tree[101];
int subtreeSize[101];
bool visited[101];

int dfs(int node);

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

    for (int i = 0; i < n - 1; i++)
    {
        int u = wires[i][0];
        int v = wires[i][1];
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // dfs를 돌려 각 노드의 노드 개수를 구한다
    // 서브트리는 처음 기준으로 구하더라도
    // 전체적인 '차'를 구하는데에는 문제가 없다
    dfs(1);

    for (int i = 2; i <= n; i++) 
    {
        // subTreeSize는 해당하는 노드의 기준으로 dfs를 돌렸을 경우, 얻을 수 있는 서브트리의 개수이다
        // 따라서 해당 subTreeSize[i]와 n - subTreeSize[i]의 차를 구함 -> n - 2 * subtreeSize[i]
        int diff = abs(n - 2 * subtreeSize[i]);
        if (diff < answer) 
        {
            answer = diff;
        }
    }

    return answer;
}

int dfs(int node) 
{
    visited[node] = true;
    subtreeSize[node] = 1; // 현재 노드 포함

    for (int child : tree[node]) 
    {
        if (visited[child] == false) 
        {
            subtreeSize[node] += dfs(child);
        }
    }

    return subtreeSize[node];
}

int main()
{
    vector<vector<int>> vec = { {1,3},{2,3},{3,4},{4,5},{4,6},{4,7},{7,8},{7,9} };

    solution(9, vec);
}

해결 아이디어

1. 특정한 edge를 없앰으로서 두 그래프를 나눈다는 점은
   다른 한쪽의 그래프에는 특정 노드가 포함된다는 점을 인지
   
2. 1번부터 dfs를 통해 서브 트리의 노드 개수를 구해준다(dfs)
   
3. 2번 노드부터 (전체 노드 개수 - 해당 노드를 포함한 그래프(서브트리)의 노드 개수)의
   절댓값을 구해준다
   (1번의 경우는 반드시 전체 개수가 나오므로 건너띔)
   
4. 전체 노드를 기준으로 계산하여 답을 구한다