[프로그래머스] 네트워크 (c++)

출처 : 코딩테스트 연습 - 네트워크 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 네트워크

풀이 방법

bfs/dfs를 반복 하면 네트워크의 개수를 알 수 있다.

for 문을 돌면서 방문하지 않은 네트워크를 발견 했을때 bfs/dfs를 수행하면 된다

#include <string>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;
int visited[201];

void bfs(int k, int n, vector<vector<int>> computers) {
    queue<int> q;
    q.push(k);
    while(!q.empty()) {
       int k = q.front();
       q.pop();
       for (int i = 0;i < n;i++) {
           if (visited[i] == -1 && computers[i][k] == 1) {
               visited[i] = 1;
               q.push(i);
           }
       }
    }
}

int solution(int n, vector<vector<int>> computers) {    
    int answer = 0;
    memset(visited, -1, sizeof(visited));
    for (int i = 0;i < n;i++) {
        if (visited[i] == -1) {
            answer++;
            bfs(i, n, computers);
        }
    }
    return answer;
}