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

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

프로그래머스

풀이

트리의 노드 갯수 n, 엣지 정보 wires 가 주어졌을 때, 트리를 둘로 나누어 각 트리의 노드 갯수 차이의 최솟값을 리턴해야합니다.

알고리즘은 아래와 같습니다.

1. 주어진 n, wires를 사용해 트리구조 graph를 생성합니다.
2. 엣지 정보는 pair 자료구조 변수 divide를 사용해 따로 저장해둡니다.
3. 모든 엣지를 순회하며 한번씩 잘라보면서 나눠진 각 트리의 노드 갯수를 카운트합니다.
   1. 재귀 dfs를 사용해 노드 방문 체크 및 group_cnt 변수 및 node_cnt 변수를 사용해 각 그룹의 노드 갯수를 카운트합니다.
   2. 새로운 노드 방문시 node_cnt 값이 올라가며, 잘라야 하는 엣지에 해당하는 경우이거나 이미 다음 노드를 방문했다면 다음 dfs로 넘어가지 않습니다.

4. 현재 엣지를 자른 경우의 노드 차이를 answer에 업데이트 하고, 다음 엣지를 자르기 위해 변수를 초기화 합니다.

 

리뷰

재귀 DFS 형태를 잘 이해하고 기억해 둬야할 필요가 있습니다. 

#include <string>
#include <vector>
#include <memory.h>

using namespace std;

vector<int> graph[101];
vector<pair<int,int>> divide;
bool visited[101];
int group_cnt; // 0 또는 1
int node_cnt[2]; // 노드 카운트 위한 변수

void dfs(int node, pair<int,int> cut){
    visited[node] = 1;  // 방문 체크
    node_cnt[group_cnt]++; // 방문 했으니 노드 갯수 카운트
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if ((node == cut.first && next == cut.second) || (node == cut.second && next == cut.first))
            // 잘라야 하는 엣지에 해당 하는 경우 다음으로 넘어가지 않음
            continue;
        if (visited[next]) // 이미 방문했다면 다음으로 넘어가지 않음
            continue;
        
        dfs(next, cut);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 1e9;
    
    for(int i=0; i < wires.size(); i++){
        int a = wires[i][0];
        int b = wires[i][1];
        graph[a].push_back(b);
        graph[b].push_back(a);
        divide.push_back({a,b});
    }
    
    for(int i=0; i<divide.size(); i++){
        // 현재 엣지
        int a = divide[i].first;
        int b = divide[i].second;
        // 모든 노드 순회하며 현재 엣지 자르고 노드 카운트
        for(int k=1; k <= n; k++) {
            if (visited[k]) 
                continue;
            dfs(k, {a,b});
            group_cnt++;
        }
        
        answer = min(answer, abs(node_cnt[0]-node_cnt[1])); //노드 차이 계산 및 answer 최소값 업데이트
        // 다음 엣지 DFS 위한 초기화
        group_cnt = 0;
        memset(visited, 0, sizeof(visited)); 
        node_cnt[0] = 0;
        node_cnt[1] = 0;
    }
    return answer;
}