[프로그래머스 고득점kit] 전력망을 둘로 나누기 (C++)

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

프로그래머스

 

이번 문제는 완전탐색 카테고리의 문제로 분류되었지만, 저는 분리집합(disjoint set) 을 통한 풀이가 더 효율적일 것 같아

Union-Find 알고리즘과 Path Compression을 통한 풀이로 제출하였습니다. 

입력으로 주어진 간선들 중 임의로 1개의 간선을 제거한 뒤, 나눠진 2개의 그룹의 구성원 수를 계산하고,

가장 차이가 적은 경우의 수를 출력하도록 구현하였습니다.

#include <string>
#include <vector>
#include<iostream>
using namespace std;
int parent[101];
int find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]); //find하며 path Compression.
    //parent 배열 값을 갱신한다.
}
void join(int x, int y) {
    int p_x = find(x), p_y = find(y);
    parent[p_x] = p_y;

}
int solution(int n, vector<vector<int>> wires) {
    int answer = -1;
    int min = 987654321;
    for (int k = 0; k < wires.size(); k++) {
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        int a, b, dif = 0;
        for (int i = 0; i < wires.size(); i++) {//k째 전선 빼고 연결
            if (i == k) {
                a = wires[i][0], b = wires[i][1];//a,b 간선제거 -> 트리가 나눠지는 2개 노드
              //  cout<<"disconnect: "<<a<<" "<<b<<endl;
                continue;
            }
            join(wires[i][0], wires[i][1]);
        }
        a = find(a);
        b = find(b);
        for (int i = 1; i <= n; i++) {

            if (find(i) == a) dif++;   //a노드와 같은 그룹
            else if (find(i) == b) dif--; //b노드와 같은그룹
            // else cout<<"error!"<<endl;
        }
        if (dif < 0) dif = (-1) * dif; //절댓값 적용

        if (dif < min)min = dif;


    }
    answer = min;
    return answer;
}