[프로그래머스] 전력망을 둘로 나누기 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차

1. 주의할 점

- N이 100개 이하다

- Tree다 → 임의의 서로 다른 두 Node A,B로 가기 위한 방법은 유일하다

 

2. 구현

- 입력받을 때, Conn[][] 배열을 통해 두 Node의 간선 여부를 파악하고 V[] 벡터를 통해 각 Node와 연결된 다른 Node를 저장한다

- N이 작기 때문에 연결되어 있는 서로 다른 두 Node A,B의 간선을 자르고 BFS를 돌린다고 가정한다

- Queue를 통해 BFS를 수행하며 Check[] 배열을 통해 각 Node의 방문여부를 체크한다

- 위의 과정을 수행할 때, Check[] 배열은 항상 초기화하하고 시작한다

#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
struct info{
    int idx,start;
};
bool conn[101][101]={false,};
bool check[101];
int sum[2];
vector<int> v[101];

int solution(int n, vector<vector<int>> wires) {
    int answer = n;
    for(int i=0;i<wires.size();i++){
        int from = wires[i][0];
        int to = wires[i][1];
        conn[from][to]=true;
        conn[to][from]=true;
        v[to].push_back(from);
        v[from].push_back(to);
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(!conn[i][j]) continue;
            queue<info> q;
            q.push({i,0});
            q.push({j,1});
            sum[0]=1;
            sum[1]=1;
            memset(check,false,sizeof(check));
            check[i]=true;
            check[j]=true;
            while(!q.empty()){
                int cidx = q.front().idx;
                int cs = q.front().start;
                q.pop();
                for(int k=0;k<v[cidx].size();k++){
                    int next = v[cidx][k];
                    if(conn[cidx][next] && !check[next]){
                        check[next]=true;
                        q.push({next,cs});
                        sum[cs]++;
                    }
                }
            }
            answer = min(answer,abs(sum[0]-sum[1]));
        }
    }
    return answer;
}