[Programmers] 전력망을 둘로 나누기 unordered_set, BFS

전력망을 둘로 나누기

오랜만에 프로그래머스 문제를 풀어보았다. 프로그래머스는 input값을 신경쓰지 않아도 된다는 장점이 있지만, 동시에 단점이라고 할 수 있다.
그래도 정답입니다! 보는 맛이 있다.

배운점

1. unordered_set의 경우 (map도 마찬가지) index로 접근이 불가능하다. 따라서 for문을 돌린다면 iter을 만들거나 for(auto i: set)의 형식으로 사용해야 한다. 또한 삽입은 insert, 삭제는 erase(value)이다.
2. abs의 라이브러리는 cmath이고, min의 라이브러리는 algorithm이다.
3. 노드 값이 최대 100이기 때문에, brute force 방식으로 모든 간선을 비교해 보는 것이 가능하다. 주어진 제한 조건을 잘 보자!

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define MAXN (100+2)
unordered_set<int>ss[MAXN];
int bfs(int wire){
    int check[MAXN]={0,};
    int cnt=0;
    queue<int>que;
    que.push(wire);
    check[wire]=1;
    while(!que.empty()){
        int data=que.front(); que.pop();
        for(auto next:ss[data]){
            if(check[next]) continue;
            check[next]=1;
            que.push(next);
            cnt++;
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    
    int answer = 0x7fffffff;
    for(int i=0;i<wires.size();i++){
        ss[wires[i][0]].insert(wires[i][1]);
        ss[wires[i][1]].insert(wires[i][0]);//양방향 간선
    }//노드간 연결
   
    for(auto wire:wires){
        ss[wire[0]].erase(wire[1]);
        ss[wire[1]].erase(wire[0]);
        
        answer=min(answer, abs(bfs(wire[0])-bfs(wire[1])));
        
        ss[wire[0]].insert(wire[1]);
        ss[wire[1]].insert(wire[0]);
    }
    return answer;
}