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

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=cpp

프로그래머스

풀이 방법

문제를 보자마자 완전 탐색 + bfs로 풀이해야겠다고 생각이 들었다. 

연결된 간선을 하나씩 끊어 가며 bfs로 두 구역의 차이를 구한 후 가장 작은 차이를 가지는 것을 저장해 두었다.

간선을 끊는 방법은 간선을 돌며 선택된 간선에서 한쪽에서 bfs를 수행할 때 다른 한쪽 구역은 방문하지 않는 방법이다. 

이렇게 양 쪽에서 각각 bfs를 수행한 후 두 지역의 차이를 구했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
vector<vector<int>> graph;
int bfs(int a, int b, int n) { // a인거 탐색, b인거랑 연결되지 않도록
    int cnt = 0; // 연결된 지역을 count
    queue<int> q;
    q.push(a);
    vector<int> visited(n+1);
    for (int i = 0;i < n+1;i++) {
        visited[i] = 0;
    }
    visited[a] = 1;
    while(!q.empty()) { // 
        int next = q.front();
        q.pop();
        for (int i = 0;i < graph[next].size();i++) {
        	// 방문 안했고 간선의 반대편 지역이 아닌경우
            if (visited[graph[next][i]] == 0 && graph[next][i] != b) {
                q.push(graph[next][i]);
                cnt++;
                visited[graph[next][i]] = 1;
            }
        }
    }
    int flag = 0;
    for (int i = 1; i < n + 1;i++) { // 구역을 나눌 수 있는지 탐색
        if (visited[i] == 0) { // 구역이 나눠진 경우
            flag = 1;
        }
    }
    if (flag == 1) {
        return cnt;
    }
    else { //구역을 못 나눈 경우
        return -1;
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 987654321; // 최대값 설정 
    graph.resize(n+1);
    for (int i = 0; i < wires.size();i++) { // 연결 그래프 만들기
        graph[wires[i][0]].push_back(wires[i][1]);
        graph[wires[i][1]].push_back(wires[i][0]);
    }
    
    for (int i = 0;i < wires.size();i++) { // 양쪽에서 bfs돌기
        int a = bfs(wires[i][0], wires[i][1], n);
        int b = bfs(wires[i][1], wires[i][0], n);
        if (a == -1 || b == -1) continue;
        answer = min(answer, abs(a - b));
    }
    return answer;
    
}