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

문제

---

 

프로그래머스

 

 

풀이

---

완전 탐색과 BFS가 섞인 문제다.

오늘도 피곤 이슈로... 대략적인 풀이만 올리고 다음에 몰아서 풀이를 올릴 예정이다.

 

우선 n이 작고, 제공되는 간선의 수도 100 보다 작기 때문에 모든 경우의 수를 다 해볼 수 있다.

그러면 첫번째부터 마지막 간선까지 선을 하나씩 제거해나가며 BFS를 돌려보면 된다.

 

문제 조건이 하나만 끊어도 둘로 나눠지게 설계되어있기에 모든 간선을 한 번씩 끊어보며 확인해보면 된다.

 

그런데 처음에는 두 번 다 돌려야 하나? 했는데 양 쪽 구간을 모두 확인한다고 두번 돌릴 필요는 없다.

n이 정해져있기 때문에 한쪽이 k개라면, 다른 한쪽은 n - k개이기 때문에, 한쪽만 돌리고 한쪽에서 나온 값을 k라고 할 때 abs(2*k -n)을 해주면 한 번의 bfs값은 쉽게 구할 수 있다.

 

이걸 그냥 모든 간선에 해주면서 비교하면 끝이다!

 

 

C++ 코드

---

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

using namespace std;

vector<int> g[101];
bool visited[101];

int bfs(int start, int n) {
    queue<int> q;
    int result = 0;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result++;
        
        for (int i = 0; i < g[current].size(); i++) {
            if(visited[g[current][i]] == true) continue;
            q.push(g[current][i]);
            visited[g[current][i]] = true;
        }
    }
    
    return abs(result * 2 - n);
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 1234567890;
    
    for (int i = 0; i < wires.size(); i++) {
        for (int j = 0; j < wires.size(); j++) {
            if (j == i) continue;
            g[wires[j][0]].push_back(wires[j][1]);
            g[wires[j][1]].push_back(wires[j][0]);
        }
        answer = min(bfs(wires[i][0], n), answer);
        memset(visited, false, sizeof(bool) * 101);
        
        for (int j = 0; j < 101; j++) {
            g[j].clear();
        }
    }
    
    return answer;
}