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

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

프로그래머스

전선 하나를 끊어 전력망을 2개로 나눴을때

각 전전력망의 개수 차의 최솟값을 구하라

 

 

주어진 wires 배열의 값중 하나를 의미 없는 값으로 바꾸고 모든 경우에 bfs 탐색을 수행

1번 송전탑 + 연결된 탑의 개수 N을 구하고

N과  (전체 전력망 개수)-N의 차가 최소가 될때 그 값을 return 한다

 

int solution(int n, vector<vector<int>> wires) {
    int answer = 999;
    for(int t=0 ; t<wires.size() ; t++){
        w=wires;
        w[t]={0,0};

w 벡터에 wires를 복사하고 임의의 값 하나를 {0,0}으로 변경

 

queue<int> q;
        q.push(1);
        counts=0;
        for(int tt=0 ; tt<101 ; tt++)
            visit[tt]=0;
        visit[1]=1;
        while(!q.empty()){
            counts++;
            int start = q.front();
            cout<<start<<" ";
            q.pop();
            for(int i=0 ; i<wires.size() ; i++){
                int w0 = w[i][0];
                int w1 = w[i][1];
                if(w0==start && visit[w1]!=1){
                    q.push(w1);
                    visit[w1]=1;
                }
                if(w1==start && visit[w0]!=1){
                    q.push(w0);
                    visit[w0]=1;
                }   
            }
        }

각각의 경우에 bfs 탐색을 수행

 

        int a = n-counts;
        int b = max(counts, n-counts);
        int c = min(counts, n-counts);
        int d = b-c;
        if(d<answer)
            answer = d;
    }
    return answer;

bfs로 구한 한 전력망의 송전탑 개수 counts와

다른 전력망의 개수는 n - counts

둘의 차를 구하고

차의 최소값을 answer에 담아 return하면 끝

 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
vector<vector<int>> w;
int visit[101];
int counts=0;
int solution(int n, vector<vector<int>> wires) {
    int answer = 999;
    for(int t=0 ; t<wires.size() ; t++){
        w=wires;
        w[t]={0,0};
        queue<int> q;
        q.push(1);
        counts=0;
        for(int tt=0 ; tt<101 ; tt++)
            visit[tt]=0;
        visit[1]=1;
        while(!q.empty()){
            counts++;
            int start = q.front();
            cout<<start<<" ";
            q.pop();
            for(int i=0 ; i<wires.size() ; i++){
                int w0 = w[i][0];
                int w1 = w[i][1];
                if(w0==start && visit[w1]!=1){
                    q.push(w1);
                    visit[w1]=1;
                }
                if(w1==start && visit[w0]!=1){
                    q.push(w0);
                    visit[w0]=1;
                }   
            }
        }
        int a = n-counts;
        int b = max(counts, n-counts);
        int c = min(counts, n-counts);
        int d = b-c;
        if(d<answer)
            answer = d;
    cout<<"->"<<counts<<" answer="<<answer<<"\n";
    }
    return answer;
}

 전체 코드