[프로그래머스/위클리 챌린지] 9주차 (C++)

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차

BFS와 구현력을 요구하는 어렵지 않은 문제였다. 예전에 네이버에 이와 비슷한 문제가 나온적이 있어서 쉽게 풀었다. 간선을 하나씩 제거한 것을 기록하기 위해 2차원 배열을 이용했다. 그 후 BFS를 이용해 트리를 탐색하는데, 체크한 간선을 구성하고 있는 노드를 탐색하려고 하면 그대로 continue 해준다. 이런식으로 나눠진 트리의 노드 수를 각각 구하고, 이들의 차의 절댓값이 최소인 것을 찾으면 된다.

 

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

vector<int> tree[101];
bool deleted[101][101];
bool visit[101];
int N, answer = INT_MAX;

int BFS(int node) {
    queue<int> q, u;
    q.push(node);
    u.push(node);
    visit[node] = true;

    while(!q.empty()) {
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < tree[now].size(); i++) {
            int next = tree[now][i];
            if(deleted[now][next] || deleted[next][now]) continue;
            if(!visit[next]) {
                q.push(next);
                u.push(next);
                visit[next] = true;
            }
        }
    }
    
    return u.size();
}

int check() {
    int order = 1, first = 0, second = 0;
    for(int i = 1; i <= N; i++) {
        if(!visit[i]) {
            if(order == 1) first = BFS(i);
            else if(order == 2) second = BFS(i);
            order++;
        }
    }
    
    memset(visit, false, sizeof(visit));
    return abs(first - second);
}

int solution(int n, vector<vector<int>> wires) {
    N = n;
    
    for(int i = 0; i < n - 1; i++) {
        tree[wires[i][0]].push_back(wires[i][1]);
        tree[wires[i][1]].push_back(wires[i][0]);
    }
    
    for(int i = 0; i < n - 1; i++) {
        int x = wires[i][0], y = wires[i][1];
        
        deleted[x][y] = true;
        deleted[y][x] = true;
        
        answer = min(answer, check());
        
        deleted[x][y] = false;
        deleted[y][x] = false;
    }
    
    return answer;
}