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

문제

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

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

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

 

문제 내용

N개의 송전탑과 이를 연결하는 N-1개의 전선이 있다.

입력으로 주어지는 송전탑들의 관계는, N-1개의 전선으로 모두 이어져있다.

이때, 전선 1개를 끊어서 송전탑을 2 부류로 나눈다.

양측의 탑의 개수의 차를 최소화 했을 때의 차이를 구하면 된다.

 

문제 풀이

주어진 N-1개의 전선을 한번씩 끊어보면 된다.

끊고 bfs를 돌리면 탑들이 2부류로 나뉘게 된다. 이때의 차를 구하는 것은 어렵지 않다.

 

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int divideTowerAndCalcNum(vector<int>arr[], int n){
    vector<int> visit(n+1,-1);
    
    queue<int> q;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(visit[i]!=-1) continue; //이미 방문함
        
        q.push(i);
        visit[i]=++cnt; //1또는 2의 값을 갖게 된다.
        
        while(!q.empty()){
            int node=q.front();
            q.pop();
            
            for(auto nxt: arr[node]){
                if(visit[nxt]!=-1) continue; //이미 방문함
                
                q.push(nxt);
                visit[nxt]=cnt;
            }
        }
    }
    
    int tower1=count(visit.begin(), visit.end(), 1);
    int tower2=count(visit.begin(), visit.end(), 2);
    
    return abs(tower1-tower2);
}

int solution(int n, vector<vector<int>> wires) {
    int diff=1000;
    
    for(int i=0;i<n;i++){ //몇번째 wire를 끊는지 결정
        
        vector<int> arr[n+1];
        for(int j=0;j<wires.size();j++){ //간선의 개수만큼만 or n-1
            if(i==j) continue;            
            
            arr[wires[j][0]].push_back(wires[j][1]);
            arr[wires[j][1]].push_back(wires[j][0]);
        }
        // 계산
        diff=min(diff, divideTowerAndCalcNum(arr, n));
    }
    
    return diff;
}