프로그래머스 lv 2. 86971 전력망을 둘로 나누기 c++

 

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

#include <bits/stdc++.h>

using namespace std;

int answer=0x7f7f7f7f;
vector<bool> vis(101);

void dfs(int idx, vector<vector<int>> wires){
    vis[idx]=true;
    for(int i=0; i<wires.size();i++){
        if(wires[i][0]==idx&&!vis[wires[i][1]]) dfs(wires[i][1],wires);
        else if(wires[i][1]==idx&&!vis[wires[i][0]]) dfs(wires[i][0],wires);
    }
}

int solution(int n, vector<vector<int>> wires){
    for(int i=0; i<wires.size();i++){
        int res=0;
        vector<vector<int>> tmp(wires);
        fill(vis.begin(),vis.end(),false);
        tmp.erase(tmp.begin()+i);
        dfs(tmp[0][0],tmp);
        for(int i=1; i<=n; i++){
            if(vis[i]) res++;
        }
        answer=min(answer,abs(res-(n-res)));
    }
    return answer;
}

 

 

+++++++++++

다른 사람의 풀이 보기를 했을때 가장 위에 올라와있는 추천수가 가장 많은 코드인데, 이 코드로 돌려보면

위의 풀이보다 훨씬 빠르다. 이 방법을 익히는것이 좋겠다. 이 방법에 익숙해지도록 하자 

#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;
}

 

람다 함수를 통해서 dfs를 solution 내부에서 정의하고 사용하는것 또한 재미있다. 유용한 형태이다. 아무래도 이 형태로 사용하는것은 그동안 알고리즘 문제풀이에서는 많이 사용해보지 않아서 내가 아직 익숙하게 사용하지 못하는 형태지만, 그래도 계속 만날때마다 익숙해지는 연습을 해보도록 하자.