[c++] 프로그래머스 - 전력망을 둘로 나누기(Level 2)

문제

코딩테스트 연습 - 전력망을 둘로 나누기

 

코드

#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;
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<=wires.size(); k++){
            if(visited[k]) continue;
            dfs(k, {a,b});
            group_cnt++;
        }
        
        if(group_cnt==2) answer = min(answer, abs(node_cnt[0]-node_cnt[1]));   //두개로 분할 되었을 때
        group_cnt = 0;
        memset(visited, 0, sizeof(visited));
        node_cnt[0] = 0, node_cnt[1] = 0;
    }

 

풀이

하나씩 전선을 끊어가며 모든 경우의 수를 탐색하였습니다. 끊을 노드 두 개를 pair를 통해서 인자 값으로 넘기고 아래 코드를 통해 끊긴 부분이라면 탐색하지 않는 방식으로 구현했습니다.

if((node==cut.first&&next==cut.second)||(node==cut.second&&next==cut.first))

 

최종적으로 group_cnt가 두개가 되면 두 전력망으로 나누어진 것이기 때문에  아래 코드를 통해 최대한 균등하게 나뉘어진 값을 갱신하면서 모든 경우의 수를 탐색했습니다.

 if(group_cnt==2) answer = min(answer, abs(node_cnt[0]-node_cnt[1]));   //두개로 분할 되었을 때