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

---

반응형

728x90

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

#include <string>
#include <vector>

using namespace std;

int dfs(int node, int ignoreNode, vector<vector<int>>& tree, vector<bool>& visited) {
    visited[node] = true;
    int count = 1;

    for (int neighbor : tree[node]) {
        if (!visited[neighbor] && neighbor != ignoreNode && neighbor != node) {
            count += dfs(neighbor, ignoreNode, tree, visited);
        }
    }

    return count;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    vector<vector<int>> tree(n + 1);
    
    for (const auto& wire : wires) {
        int w1 = wire[0];
        int w2 = wire[1];
        tree[w1].push_back(w2);
        tree[w2].push_back(w1);
    }

    for (const auto& wire : wires) {
        int w1 = wire[0];
        int w2 = wire[1];

        vector<bool> visited(n + 1, false);
        
        int subtreeSize = dfs(w1, w2, tree, visited);
        int otherSize = n - subtreeSize;

        answer = min(answer, abs(subtreeSize - otherSize));
    }

    return answer;
}

---

📝 풀이

wires를 기반으로 양방향 트리를 생성합니다.

각 전선을 끊었을 때 두 네트워크 차이를 계산합니다.

w1과 w2의 전선을 끊고 dfs로 한 쪽 서브 트리를 계산합니다.

나머지 서브 트리 크기는 전체 노드 수에서 서브 트리 크기를 빼서 계산합니다.

두 개의 트리 중 작은 크기로 answer 값을 갱신합니다.

최종적으로 answer을 return 합니다.