(c++)프로그래머스 코딩테스트 연습 - 네트워크

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

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

[풀이]

bfs탐색으로 풀었다.

예제를 보면 컴퓨터 1대만 있어도 네트워크로 치는 것을 알 수 있다. 그래서 N번 for문을 돌리며 아직 네트워크임을 체크하지 않은 컴퓨터가 있으면 bfs로 이어진 네트워크 모두를 체크하고, 네트워크의 개수는 bfs가 호출되는 개수로 구하였다.

 

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

using namespace std;

int N;
vector<vector<int>>Computers;
bool check[200];

void bfs(int startx){
    queue<int>q;
    q.push(startx);
    check[startx]=true;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<N;i++){
            if(x==i)
                continue;
            //연결되어 있다면
            if(Computers[x][i]==1&&check[i]==false){
                check[i]=true;
                q.push(i);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    N=n;
    Computers=computers;
    for(int i=0;i<N;i++){
        //아직 네트워크로 세어지지 않은 컴퓨터가 있다면
        if(check[i]==false){
            bfs(i);
            answer++;
        }
    }
    return answer;
}