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

문제 링크 : 전력망을 둘로 나누기

한창 부스트캠프를 진행하느라 알고리즘 공부에 소홀해진 것 같아서 슬슬 시간날 때 한 문제씩 풀어야겠다..

[문제 접근]

레벨2 문제로 문제에 트리가 적혀있어서 겁먹었는데 읽다보니 n이 작아서 그냥 브루트포스로 풀어도 풀리는 문제였다.

먼저 연결된 전력망들을 vector로 나타내주고 wires를 돌면서 하나씩 끊고 비교해주면 풀리는 간단한 문제이다.

[1, 3]을 끊는다면 1에서 출발, 3에서 출발
총 2번을 체크해야하기 때문에 체크하는 함수를 만들고 값을 비교했다.

[소스 코드]

#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

vector<int> arr[101];

int countWire(int start, int block) {
    int cnt=1;
    int visit[101];
    for(int i=0 ; i<101 ; i++) visit[i] = 0;
    
    queue<int> q;
    q.push(start);
    visit[start]=1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        
        for(int i=0 ; i<arr[x].size() ; i++) {
            int next = arr[x][i];
            if(next==block || visit[next]==1) continue;
            q.push(next);
            visit[next]=1;
            cnt++;
        }
    }
    
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 200;
    for(vector<int> wire : wires) {
        int v1 = wire[0], v2 = wire[1];
        arr[v1].push_back(v2);
        arr[v2].push_back(v1);
    }
    
    for(vector<int> wire : wires) {
        int v1=wire[0], v2=wire[1];
        answer = min(answer, abs(countWire(wire[0], wire[1])-countWire(wire[1], wire[0])));
    }
    
    return answer;
}