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

 

 

Code

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
 
using namespace std;
vector<vector<int>> v(101);
bool visited[101];
 
void dfs(vector<int> except, int index){
    visited[index] = true;
    
    for(int i=0;i<v[index].size();i++){
        int next = v[index][i];
        if(visited[next])
            continue;
        if(index==except[0] && next==except[1])
            continue;
        if(index==except[1] && next==except[0])
            continue;
        dfs(except,next);
    }
}
 
int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    
    for(int i=0;i<wires.size();i++){
        v[wires[i][0]].push_back(wires[i][1]);
        v[wires[i][1]].push_back(wires[i][0]);
    }
    
    for(int i=0;i<wires.size();i++){
        memset(visited,false,sizeof(visited));
        //1번부터 순회
        dfs(wires[i],1);
        
        //visited true인 곳 세기
        int true_cnt=0;
        for(int i=1;i<=n;i++){
            if(visited[i])
                true_cnt++;
        }
        answer = min(answer,abs(true_cnt-(n-true_cnt)));
    }
    return answer;
}