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

 

나름 괜찮게 풀었다.

추천 수를 가장 많이 받은 다른 분의 풀이가 나랑 같았다. 뿌듯했다.

#include <string>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int counter = 0;
bool visit[101];

void dfs(vector<vector<int>>& v, int num) {
    
    counter++;
    visit[num] = true;
    
    for(int i = 0; i < v[num].size(); i++) {
        
        if(!visit[v[num][i]]) {
            
            dfs(v, v[num][i]);
        }
        
    }
    
}

int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    
    for(int i = 0; i < n - 1; i++) {
        
        vector<vector<int>> v(n + 1, vector<int>());
        memset(visit, 0, sizeof(visit));
        counter = 0;
        
        for(int j = 0; j < n - 1; j++) {
            
            if(i == j)
                continue;
            else {
                // 양방향 연결
                v[wires[j][0]].push_back(wires[j][1]);
                v[wires[j][1]].push_back(wires[j][0]);
            }
            
        }
        
        
        dfs(v, 1);
        if(abs(counter - abs(n - counter)) <= answer)
            answer = abs(counter - abs(n - counter));
        
    }
    
    
    return answer;
}

dfs는 한 번으로도 풀 수 있다.