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

 

 

 

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

프로그래머스

 

이 문제는 n이 100이라서 충분히 완전 탐색으로 풀 수 있을 것이라고 생각했다. (유형도 완탐이긴 했지만..ㅋ)

입력되는 벡터 배열인 wires는 간선을 나타내는 것이기 때문에 이 벡터 원소를 하나씩 빼서 2 그룹의 정점 개수 차이를 구하면 된다.

tmp 벡터 배열을 하나 만들어서 erase함수로 간선을 하나 지우고 1부터 n 정점을 돌면서 방문하지 않은 정점이라면 BFS를 시작한다. 

BFS 내에서 살짝 헤맸는데, 평소엔 vector<int> v [n]과 같은 형식의 2차원 벡터를 사용했어서 자연스럽게

for(int i=0; i<v[x].size(); i++){
    int y = v[x][y];
    //...
}

 

이런 식으로 그냥 넣었다가 이상한 답을 얻었다..^^ (정신차리기

 

또 조심할 것은 

1 → 2, 2 → 3 이렇게 이어진 것이 아니라

1 → 2, 3 → 2 이렇게 이어진 경우 카운팅을 덜 할 수 있다.

그러므로 꼭 tmp [i][0] == x와 tmp [i][1] == x 둘 다 확인해주면 쉽게 풀린다.

 

(vector <int> v [n] 형식이었다면,, 필요 없는 부분인데...ㅋ...ㅠ)

 

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
bool visit[101];
queue<int> q;

int BFS(int start, vector<vector<int>> tmp){
    int cnt = 1;
    visit[start] = true;
    q.push(start);
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=0; i<tmp.size(); i++){
            if(tmp[i][0] == x){
                int y = tmp[i][1];
                if(!visit[y]){
                    cnt++;
                    visit[y] = true;
                    q.push(y);
                }
            }else if(tmp[i][1] == x){
                int y = tmp[i][0];
                if(!visit[y]){
                    cnt++;
                    visit[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    for(int i=0; i<n-1; i++){
        vector<vector<int>> tmp = wires;
        tmp.erase(tmp.begin() + i);             //간선 하나 제거
        memset(visit, false, n+1);              //visit 초기화
        int firstCnt = 0, secondCnt = 0;        //각 집합 정점 개수 초기화
        bool flag = false;
        for(int j=1; j<=n; j++){
            if(!visit[j]){
                if(!flag){
                    firstCnt = BFS(j, tmp);
                    flag = true;
                }else{
                    secondCnt = BFS(j, tmp);
                }
            }
        }
        answer = min(answer, abs(firstCnt - secondCnt));
    }
    return answer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << solution(9, {{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {4,7}, {7,8}, {7,9}}) << '\n'; //3
//    cout << solution(4, {{1,2}, {2,3}, {3,4}}) << '\n'; //0
//    cout << solution(7, {{1,2}, {2,7}, {3,7}, {3,4}, {4,5}, {6,7}}) << '\n'; //1
    return 0;
}