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

문제

 

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

프로그래머스

 

 

문제풀이

 

DFS+재귀를 이용하여 풀었다.

DFS를 통해 트리를 탐색한다.

탐색이 모두 끝나면 재귀를 통해 현재 노드가 새로운 노드의 루트가 된다고 가정한다.

트리에서 현재 노드와 잇는 간선을 끊는다고 생각하면 된다.

그렇게 되면 새로 생긴 트리의 노드 개수는 재귀를 통해 누적된 값들의 합이 된다.

 

예제 1번이다. 본문의 그림에선 4-7의 간선을 끊었지만, 3-4의 간선을 끊는 것도 답이다.

설명을 위해 3-4의 간선을 끊는 것을 예로 든다.

DFS(4)을 하게 되면 next_node에는 5, 6, 7이 있다.

그리고 node_cnt에는 본인을 포함한 1 + DFS(5) + DFS(6) + DFS(7)이 된다.

이렇게 되면 4를 루트로 하는 트리를 구성하는 총노드의 개수를 구할 수 있다.

 

그리고 총노드의 개수는 N이므로 나머지 트리의 노드 개수는 N - node_cnt가 된다.

따라서 answer를 answer와 N - node_cnt와 node_cnt의 차의 절댓값 중 작은 값으로 갱신하면 된다.

 

처음 DFS를 시작할 때는 노드 중에 아무 노드나 넣으면 된다.

 

코드

#include <string>
#include <vector>
using namespace std;
vector<vector<int>>tree;
vector<bool>visited;
int N, answer;

int DFS(int node) {
    int node_cnt(1);
    for (int idx = 0; idx < tree[node].size(); ++idx) {
        int next_node = tree[node][idx];
        if (visited[next_node] == true) continue;
        else {
            visited[next_node] = true;
            node_cnt += DFS(next_node);
        }
    }
    answer = min(answer, abs(N - node_cnt - node_cnt));
    return node_cnt;
}

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

    tree = vector<vector<int>>(N + 1);
    visited = vector<bool>(N + 1, false);

    for (int idx = 0; idx < wires.size(); ++idx) {
        int node1 = wires[idx][0];
        int node2 = wires[idx][1];
        tree[node1].push_back(node2);
        tree[node2].push_back(node1);
    }
    
    DFS(1);
    return answer;
}