[프로그래머스 문제풀이] 23. 전력망을 둘로 나누기

나의 풀이

DFS 알고리즘을 사용하여 문제를 해결했다.
이전 문제에서 사용했던 DFS 알고리즘과는 조금 결이 다른 것이
이전 문제에서는 컨테이너의 접근 순서를 완전 탐색했고
이번 문제는 그래프의 노드를 완전 탐색했다.

그래프를 만들려면 정점마다 모든 선을 표현해야 한다.
데이터가 다음과 같이 주어진다면

{{1, 3}, {2, 3}, {3, 4}, {4, 5}, {4, 6}, {4, 7}, {7, 8}, {7, 9}}

아래와 같이 데이터 형식을 변경한다.

{{1, {3}}, {2, {3}}, {3, {1, 2, 4}}, {4, {3, 5, 6, 7}}, {5, {4}}, {6, {4}}, {7, {4, 8, 9}}, {8, {7}}, {9, {7}}}

int와 vector의 쌍으로 표현되기 때문에 map 컨테이너를 사용하였다.

---

위의 그래프에서 연결된 선을 하나씩 끊어 보면서 cnt로 정점이 몇개 들어있는 지 세고 cnt를 이용하여 답을 구했다.
아래는 그래프를 탐색하는 DFS 알고리즘이다.

void dfs(int h) {
    ++cnt;

    visit[h] = 1;
    for (int i = 0; i < g_graph[h].size(); i++) {
        int y = g_graph[h][i];
        if (!visit[y]) dfs(y);
    }
}

---

🎉완성코드

#include <string>
#include <vector>
#include <map>

using namespace std;

map<int, vector<int>> g_graph;
int cnt = 0;

vector<int> visit;
void dfs(int h) {
    ++cnt;

    visit[h] = 1;
    for (int i = 0; i < g_graph[h].size(); i++) {
        int y = g_graph[h][i];
        if (!visit[y]) dfs(y);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int min_value = 100;

    for (size_t ex = 0; ex  < wires.size(); ex ++)
    {
        map<int, vector<int>> graph;

        for (size_t i = 0; i < wires.size(); i++)
        {
            if (ex!=i)
            {
                graph[wires[i][0]].push_back(wires[i][1]);
                graph[wires[i][1]].push_back(wires[i][0]);
            }
        }

        g_graph = graph;
        visit.clear();
        visit.resize(n + 1);

        dfs(1);

        int val = 2 * cnt - n;
        val = val < 0 ? val * -1 : val;

        min_value = min(min_value, val);

        cnt = 0;
    }

    return min_value;
}

---

추천을 많이 받은 풀이

람다 함수를 이용하여 함수 안에 또 다른 함수를 만들 수 있다는 것을 알게 되었다.
매개변수로 많은 것을 넘겨주면 불편해서 전역변수로 빼낼 때가 많았는데
함수 안에 함수를 만든다면 전역변수로 빼내거나 매개변수로 넘겨줄 필요 없이 함수를 사용할 수 있다.
앞으로 이런 형식을 많이 애용해야겠다.

---

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

전력망을 둘로 나누기 문제 링크