[Algorithm] Programmers :: 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 

프로그래머스

int DFS(vector<vector<int>>& graph, int node, int parentNode) 
{
    int count = 1;
 
    for (int i = 0; i < graph[node].size(); i++)
    {
        if (graph[node][i] == -1) continue;
        if (graph[node][i] == parentNode) continue; 
 
        count += DFS(graph, graph[node][i], node);
    }
 
    return count;
}
 
 
int solution(int n, vector<vector<int>> wires) {
    int answer = 100000;
 
    vector<vector<int>> graph(101);
 
    for (int i = 0; i < wires.size(); i++)
    {
        int first = wires[i][0];
        int second = wires[i][1];
 
        graph[first].push_back(second);
        graph[second].push_back(first);
    }
 
    for (int i = 0; i < wires.size(); i++)
    {
        vector<vector<int>> tempGraph = graph;
 
        int first = wires[i][0];
        int second = wires[i][1];
 
        for (int i = 0; i < tempGraph[first].size(); i++)
        {
            if (tempGraph[first][i] == second)
            {
                tempGraph[first][i] = -1;
            }
        }
 
        for (int i = 0; i < tempGraph[second].size(); i++)
        {
            if (tempGraph[second][i] == first)
            {
                tempGraph[second][i] = -1;
            }
        }
 
        int firstGroup = DFS(tempGraph,first, -11);
        int secondGroup = DFS(tempGraph, second, -11);
        int absValue = abs(firstGroup - secondGroup);
 
        if (absValue <= answer) answer = absValue;
    }
 
    return answer;
}

그냥 아주 무난하게 푼 것 같다.

wires값으로 먼저 그래프모델링 한 다음, 다시 wires돌면서 연결을 끊어주고, 나눠진 두 그룹에 대해서 탐색을 진행했다.

문제에 '트리'라고 강조된 이유는, 3-4 라는 전선을 끊는 순간, 두 그룹은 각각 3과 4를 루트노드로 한 트리가 형성되기 때문인 것 같다. 그래서 DFS탐색을 진행할 때 부모노드로 다시 올라가는 경우만 제외시키면 따로 방문체크를 할 이유가 없다.