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

문제

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

프로그래머스

 

풀이

포인트는 자를 전력망을 방문처리 해두는 것!

그것 외에는 일반 bfs와 같다

bfs 문제를 오랜만에 풀어서 실수했던 것은 cnt를 증가시킬 때

큐에서 팝 할 때 증가 시켜야 하는데, 방문하지 않는 노드 발견했을 때 증가시켜서 틀렸었다.

 

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;
vector<int> graph[101];
bool visited[101];
int cnt=0;

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

int solution(int n, vector<vector<int>> wires) {
    int answer = 987654321;
    int len = wires.size();
    for(int i=0; i<len; i++) {
        graph[wires[i][0]].push_back(wires[i][1]);
        graph[wires[i][1]].push_back(wires[i][0]);
    }
    for(int i=0; i<len; i++) {
        cnt=0;
        fill_n(visited,101,false);
        int v1 = wires[i][0];
        int v2 = wires[i][1];
        bfs(v1,v2);
        int diff = abs(n-2*cnt);
        if(diff<answer) answer=diff;
        
    }
    return answer;
}