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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 bfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. 송전탑의 전선 정보를 info 벡터에 저장

2. 전선을 하나씩 끊어가면서 bfs 수행하여 하나의 전력망의 송전탑 개수를 계산

• 끊은 전선의 양쪽 송전탑은 방문 체크 visited[v1] = true; visited[v2] = true;
• 방문하지 않은 송전탑이면 cnt++

3. 두 전력망의 차이가 answer보다 작다면 answer 갱신

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#include <cmath>
#include <queue>
#define MAX 101

using namespace std;

int cnt;
vector<int> info[MAX];

void bfs(int v1, int v2) {
    queue<int> q;
    vector<bool> visited(MAX);
    
    q.push(v1);
    visited[v1] = true;
    visited[v2] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int i=0; i<info[node].size(); i++) {
            int node2 = info[node][i];
                                                 
            if (visited[node2]) continue;
            
            cnt++;
            q.push(node2);
            visited[node2] = true;
        }
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = MAX;
    
    for (auto wire: wires) {
        info[wire[0]].push_back(wire[1]);
        info[wire[1]].push_back(wire[0]);
    }
    
    for (auto wire: wires) {
        cnt = 1;
        int v1 = wire[0];
        int v2 = wire[1];
       
        bfs(v1, v2);
        answer = min(answer, abs(2 * cnt - n));
   }
    
    return answer;
}

 

프로그래머스 - 결과 화면