[PG] 전력망을 둘로 나누기 [C++]

 

프로그래머스

 

머리 아파서 좀 대충 풀었다

 

왜인지는 모르겠지만 게리맨더링이 생각나는 문제였다.

 

전선 개수가 최대 99개여서 하나하나 다 끊어보는 방법이 가장 먼저 떠올랐다.

 

1. 부모 배열과 부모를 찾는 함수 작성(분리집합)

2. 매 케이스마다 두 집합의 크기를 구해 차가 답보다 작은지 확인하자.

3. 전선 배열을 돌면서, 해당 전선을 제외하고 모든 전선을 확인해 집합을 둘로 나눈다.

4. 부모 배열을 초기화한다.

 

이렇게 작성했는데, 통과하고 다른 사람 풀이를 보니 dfs 한 번만으로 해결했더라...

• 전선을 모두 확인해 트리를 만든 후, 임의의 송전탑 하나를 기준으로 잡고 dfs를 돌린다.
• dfs 내부에서, 송전탑마다 자신 다음에는 몇 개의 송전탑이 있는지 반환(리프 노드라면 1 반환)
• 이렇게 한 후, 모든 전선을 확인하며 해당 전선을 끊었을 때 두 집합의 차를 구한다.

dfs를 사용한 풀이가 훨씬 좋아 보인다...

 

 

코드

#include <string>
#include <vector>

using namespace std;

int parent[101];

int findParent(int x) {
    if (parent[x] < 0) {
        return x;
    } else {
        return parent[x] = findParent(parent[x]);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    for (int i = 0; i < wires.size(); i++) {
        fill(parent + 1, parent + n + 1, -1);
        for (int j = 0; j < wires.size(); j++) {
            if (i == j) {
                continue;
            }
            int p1 = findParent(wires[j][0]);
            int p2 = findParent(wires[j][1]);
            if (p1 < p2) {
                parent[p1] += parent[p2];
                parent[p2] = p1;
            } else {
                parent[p2] += parent[p1];
                parent[p1] = p2;
            }
        }
        int g1 = 0, g2 = 0;
        for (int i = 1; i < n + 1; i++) {
            if (parent[i] < 0) {
                if (g1 == 0) {
                    g1 = -parent[i];
                } else {
                    g2 = -parent[i];
                }
            }
        }
        answer = min(answer, abs(g1 - g2));
    }
    return answer;
}