(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 네트워크 답

programmers.co.kr/learn/courses/30/lessons/43162

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

bfs문제였습니다.

 

풀이방법

 1. bfs의 호출 개수가 곧 네트워크의 개수가 됩니다.

 2. 연결된 인접행렬의 정점을 계속 q에 push하면서 ck배열로 방문했음을 체크해줍니다.

 

Code

#include <bits/stdc++.h>

using namespace std;
void bfs(int x, int ck[], vector<vector<int>> &computers){
    queue <int> q;
    q.push(x);
    ck[x] = 1;
    while(!q.empty()){
        int num = q.front();
        q.pop();
        for(int next = 0; next < computers[num].size(); next++){
            if(computers[num][next] && !ck[next]){
                q.push(next);                
                ck[next] = 1;
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int ck[201];
    memset(ck,0,sizeof(ck));
    for(int i = 0; i < computers.size(); i++){
        if(!ck[i]){
            bfs(i,ck,computers);
            answer++;
        }
    }
    return answer;
}