[프로그래머스 위클리챌린지 9주차] 전력망을 둘로 나누기(C++)

코딩테스트 연습

처음에는 좀 막막했는데 금방 풀이를 떠올릴 수 있었다. 

 간선의 개수가 최대 100개밖에 되지 않아서 모든 경우를 다 탐색해보고 가장 차이가 적게 나는 경우를 찾아주었다. 처음에 인접 그래프를 떠올리고 초기화하는데 크기를 wires.size()로 입력해버려서 자꾸 Segmentation fault가 발생했다. 송전탑은 1번부터 시작하므로 wires.size() 크기로 벡터를 선언하는경우 n번째 송전탑의 그래프를 저장할 때 에러가 발생한다. 

 인접그래프를 만들고 난 뒤에는 bfs로 간단하게 순회가 가능하다. 차이가 음수일 수 있으니 abs()를 이용해 절댓값을 얻어주었다. 만약 송전탑 개수의 차이가 0또는 1이면 가장 적은 차이이므로(송전탑의 개수가 짝수일 때는 0, 홀수일때는 1) 바로 탐색을 종료한다. 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;

bool visited[101];

int solution(int n, vector<vector<int>> wires) {
    
    queue<int> q;
    int answer = 100;
    for(int i=0;i<wires.size();i++){
        vector<vector<int>> adj(wires.size()+5,vector<int>());
        memset(visited, false, sizeof(visited));
        for(int j=0;j<wires.size();j++){
            if(i==j) continue;
            adj[wires[j][0]].push_back(wires[j][1]);
            adj[wires[j][1]].push_back(wires[j][0]);
        }
        q.push(1);
        int tmp=1;
        visited[1]=true;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int k=0;k<adj[cur].size();k++){
                if(visited[adj[cur][k]]) continue;
                q.push(adj[cur][k]);
                visited[adj[cur][k]]=true;
                tmp++;
            }
        }
        
        tmp=abs(2*tmp-n);
        if(tmp<answer) answer=tmp;
        if(answer==0||answer==1) break;
    }
    
    return answer;
}