[프로그래머스 lv3] 네트워크 풀이

해설

bfs(너비 우선 탐색)을 수행하면 한번에 하나의 그래프를 탐색할 수 있다.

visited 배열에 탐색한 노드를 체크할 때, 특정 노드를 아직 체크하지 않았다면 해당 노드를 루트노드로 하는 새로운 그래프를 탐색할 수 있다는 뜻이다.

따라서, 모든 노드를 순회하면서 해당 노드가 이미 체크되었는지 확인하고, 체크되지 않았다면 이를 루트노드로 하는 새로운 그래프를 bfs로 탐색한다.

새로운 그래프를 순회할 때마다 네트워크 개수를 1 증가시키고 총 네트워크 개수를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cctype>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

void bfs(int st, vector<bool>& visited, const vector<vector<int>> computers) {

    queue<int> q;
    q.push(st);
    visited[st] = true;

    while (!q.empty()) {

        int cur = q.front();
        q.pop();

        for (int i=0; i<computers[cur].size(); i++) {
            if (!computers[cur][i]) continue;
            if (visited[i]) continue;
            visited[i] = true;
            q.push(i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {

    vector<bool> visited(n, false);

    int cnt = 0;
    for (int i=0; i<n; i++) {
        if (visited[i]) continue;
        //i번 노드를 루트노드로 하는 새로운 그래프 탐색
        cnt++;
        bfs(i, visited, computers);
    }
    return cnt;
}