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

1. 문제

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

2. 풀이

2-1. 문제를 읽고 이해하기

n개의 송전탑(정점)이 전선(간선)을 통해 하나의 트리 형태로 연결되어 있음.

전선(간선)들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할(=간선 1개를 제거해서 2개의 트리로 분할)

이때, 두 전력망이 갖게 되는 송전탑(정점)의 개수를 최대한 비슷하게 맞추고자 한다.

 

<주어지는 것>

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다.

 

<목표>

전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때,

두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

2-2. 계획 세우기

보자마자 전에 풀어봤던 문제랑 비슷한 문제라고 생각했다.

[코드트리] 최소 스패닝 트리 분할 C++

다른 점이라고 하면 간선의 가중치가 아닌 정점의 갯수를 비슷하게 남겨야 한다는 것이다.

문제 유형에서 완탐이라고 했으므로

간선 전체를 돌면서 해당 간선이 없는 경우 union find를 이용해서 2개의 그룹 연결

두 트리의 정점 갯수 차이 갱신(두 트리의 정점 갯수가 비슷해야 하므로 차이를 abs 후, min으로 갱신)

 

3. 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int myFind(int x, vector<int>& uf){
    if(uf[x]==x) return x;
    return uf[x]=myFind(uf[x], uf);
}

void myUnion(int x, int y, vector<int>& uf){
    x = myFind(x, uf), y = myFind(y, uf);
    if(x==y) return;
    uf[x]=y;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    
    for(int remove=0; remove<wires.size(); remove++){
        // uf배열 생성 및 초기화
        vector<int> uf(n+1);
        for(int v=0; v<=n; ++v){
            uf[v]=v;
        }
        
        // 간선 연결
        for(int connect=0; connect<wires.size(); connect++){
            // 연결하지 않을 간선은 건너뜀
            if(connect==remove) continue;
            int a = wires[connect][0], b = wires[connect][1];
            myUnion(a, b, uf);
        }
        
        // 트리에 연결된 정점의 개수
        int root1=myFind(uf[1], uf);
        int cnt1=0, cnt2=0;
        for(int v=1; v<=n; v++){
            if(myFind(uf[v], uf)==root1) cnt1++;
            else cnt2++;
        }
        answer = min(answer, abs(cnt1-cnt2));
    }
    
    return answer;
}