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

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

n : 9
wires : [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
result : 3

위와 같이 그래프가 주어졌을 때, 1개의 선을 자른다.
그 때 나눠진 두 전력망의 개수 차이가 가장 작은 경우 그 차이를 리턴해주면 된다.

먼저 wires에서 제외할 노선을 1개 정한다.

• 0 ~ n-1까지 n번 수행

1개의 node를 시작점으로 해서, 이어져있는 노드를 queue에 넣어가면서 클러스터링하듯 bfs를 해주면 된다.
그 후, 해당 wire 집단에 속하는 노드 개수만 구하면 나머지 집단은 굳이 구할 필요 없이 n에서 빼주면 된다.

그래프 구현을 빡세게 해본적이 없어서 살짝 비효율적인 것 같기도 하고, 좀 공부해봐야 할 것 같다.

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

struct pos {
    int row;
    int col;
};

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;

    n = n + 1;
    for(int i=0;i<wires.size();i++) {
        vector<vector<int>> v;
        for(int j=0;j<wires.size();j++) {
            if(i != j) 
                v.push_back( {wires[j][0], wires[j][1]} );
        }
        
        int graph[n][n];
        for(int j=0;j<n;j++)
            memset(graph[j], 0, sizeof(graph[j]));
        
        for(int j=0;j<v.size();j++) {
            graph[v[j][0]][v[j][1]] = 1;
            graph[v[j][1]][v[j][0]] = 1;
        }
        
        queue<vector<int>> q;
        q.push( {v[0][0], v[0][1]} );
        graph[v[0][0]][v[0][1]] = -1;
        graph[v[0][1]][v[0][0]] = -1;
        
        int visit[110]; memset(visit, 0, sizeof(visit));
        visit[v[0][0]] = 1;
        visit[v[0][1]] = 1;
        while(1) {
            if(q.empty())
                break;
            
            vector<int> node = q.front(); q.pop();
            
            for(int j=0; j<n; j++) {
                if(graph[node[0]][j] == 1) {
                    q.push( { node[0], j} );
                    graph[node[0]][j] = -1;
                    graph[j][node[0]] = -1;
                    visit[node[0]] = 1;
                    visit[j] = 1;
                }
            }
            for(int j=0; j<n; j++) {
                if(graph[node[1]][j] == 1) {
                    q.push( { node[1], j} );
                    graph[node[1]][j] = -1;
                    graph[j][node[1]] = -1;
                    visit[node[1]] = 1;
                    visit[j] = 1;
                }
            }
        }
        int num1 = 0, num2 = 0;
        for(int j=0;j<n;j++) {
            if(visit[j] == 0)
                continue;
            num1++;
        }
        num2 = n - num1 - 1;
        answer = min(abs(num1 - num2), answer);
    }
    return answer;
}