[프로그래머스/C++] 전력망을 둘로 나누기 BFS / 유니온파인드

문제 설명

---

문제설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요

 

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

---

문제 풀이

---

트리형태가 보장되어있어 BFS나 DFS로 쉽게 서칭이 가능한데 DFS를 사용하면 내 아래 노드의 갯수를 한 눈에 파악할 수 있어 1번의 서칭으로 정답을 도출할 수 있다.

 

나같은 경우 처음에는 BFS를 이용하여 와이어를 1개씩 끊을 때마다 서칭하고 최대최소를 비교했다.

두번 째 풀어나갈 때는 유니온 파인드를 이용하였고 트리에서 1개의 노선을 끊어 2개의 트리를 만든다고 생각하였을 때, 최대 크기의 트리와 전체에서 그 트리만큼을 뺀 크기의 트리가 생성되므로 (max) - (n - max)의 절대값을 구하는 것으로 정답을 도출할 수 있다.

---

코   드

---

BFS

#include <string>
#include <vector>
#include <math.h>
#include <queue>
using namespace std;
/*
* 근거. wire는 최대 100개 이하이며 각각을 기준으로 완전탐색은 최악 100회 이하
* 10000번이므로 1초 이내이니까 완전탐색 때려보자!
*/

//sp: staring_point cp: cutting_point
int BFS(vector< vector<int> > &tree, int sp, int cp) {
    int cnt = 1 ;
    queue<int> que ;
    vector<bool> visited(101) ;
    visited[sp] = 1 ;
    
    for(int branch : tree[sp])
        if(!visited[branch] && branch != cp) {
                visited[branch] = 1 ;
                que.push(branch) ;
                cnt++ ;
            }
    
    while(!que.empty()) {
        int front = que.front() ;
        que.pop() ;
        
        for(int branch : tree[front])
            if(!visited[branch]) {
                visited[branch] = 1 ;
                que.push(branch) ;
                cnt++ ;
            }
    }
    
    return cnt ;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    // 1. 트리 완성하기
    vector< vector<int> > tree(101) ;
    
    for(vector<int> wire : wires) {
        tree[wire[0]].push_back(wire[1]) ;
        tree[wire[1]].push_back(wire[0]) ;
    }
    
    
    // 2. 각 wire를 기준으로 끊어내서 양옆 사이즈 구하기
    // 3. 사이즈 차이 최소를 정답으로.
    for(vector<int> wire : wires) {
        int rhs = BFS(tree, wire[0], wire[1]) ;
        int lhs = BFS(tree, wire[1], wire[0]) ;
        
        if(abs(rhs - lhs) < answer)
            answer = abs(rhs - lhs) ;
    }
    
    return answer;
}

Union-Find

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <numeric>
using namespace std;

vector<int> parent ;
vector<int> ranking ;
int rank_max ;

int Find(int num) {
    if(parent[num] == num) return num ;
    
    return Find(parent[num]) ;
}

void Union(int lhs, int rhs) {
    int l = Find(lhs) ;
    int r = Find(rhs) ;
    if(l != r) {
        if(ranking[l] >= ranking[r]) {
            parent[r] = l ;
            ranking[l] += ranking[r] ;
            rank_max = ranking[l] ;
        }
        else {
            parent[l] = r ;
            ranking[r] += ranking[l] ;
            rank_max = ranking[r] ;
        }
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 10e3;
    
    for(int i = 0 ; i < wires.size() ; i++) {
        parent = vector<int>(n + 1) ;
        iota(parent.begin(), parent.end(), 0) ;
        
        ranking = vector<int>(n+1, 1) ;
        rank_max = 1 ;
        
        for(int j = 0 ; j < wires.size() ; j++) if(i != j) {
            Union(wires[j][0], wires[j][1]) ;
        }

        answer = min(answer, abs(2 * rank_max - n)) ;
    }
    return answer;
}

---

느낀점: 좀 더 생각하고 멋지게 코드를 짜는 연습을 해야겠다.

링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=cpp

프로그래머스