[프로그래머스] 완전탐색 - 전력망을 둘로 나누기

문제

 

풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/************************
 n     : 송전탑의 개수
 wires : 전선 정보 
*************************/

int g[101][101] = {0};
vector<bool> visited;

int dfs(int index, int n){
    
    if(visited[index]) 
        return 0;
    
    visited[index] = true;
    int count = 1;
    for(int i=1; i<=n; i++){
        if(g[index][i]){
            count += dfs(i, n);
        }
    }
    
    return count;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    
    for(int i=0; i<wires.size(); i++){
        int x = wires[i][0];
        int y = wires[i][1];
        g[x][y] = g[y][x] = 1;
    }
    
    for(int i=0; i<wires.size(); i++){
        int x = wires[i][0];
        int y = wires[i][1];
        g[x][y] = g[y][x] = 0;
    
        visited.assign(n+1, false);
        vector<int> part;
        
        for(int j=1; j<=n; j++){
            int val = dfs(j, n);
            if(val == 0) continue;
            part.push_back(val);
        }
        
        answer = min(answer, abs(part[0] - part[1]));
        if(answer == 0) break;
        g[x][y] = g[y][x] = 1;
    }    

    return answer;
}

 

모든 그래프를 탐색하기 위해 dfs를 사용했다.

트리를 2차원 배열에 넣어주었고, 전선을 끊을 때는 값을 0으로 한 후 탐색이 끝나면 다시 1로 값을 바꿔주었다.

두 송전탑 개수의 차이가 0일 경우 최솟값이므로 더 이상 탐색을 하지 않고 break 하여 나온다.  

 

 

 

---

다른 사람 풀이

#include <bits/stdc++.h>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
    vector<vector<int>> graph(n + 1);
    for(int i = 0; i < (int)wires.size(); i++) {
        int u = wires[i][0];
        int v = wires[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> siz(n + 1);
    function<void(int, int)> dfs = [&](int cur, int prev)  -> void {
        siz[cur] = 1;
        for(int nxt : graph[cur]) {
            if(nxt == prev) continue;
            dfs(nxt, cur);
            siz[cur] += siz[nxt];
        }
    };
    dfs(1, -1);
    int answer = INT_MAX;
    for(int i = 1; i <= n; i++) {
        for(int j : graph[i]) {
            int l = siz[j];
            int r = n - siz[j];
            answer = min(answer, abs(l - r));
        }
    }
    return answer;
}