[Programmers] 네트워크

Level 3

• 문제
  
  

• 코드

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int check[n];
    queue<int> q;
    for(int i=0; i<n; i++){
        check[i] = 0;
    }
    
    for(int i=0; i<n; i++){
        if(check[i]==1) continue;
        
        answer++;
        q.push(i);
        while(!q.empty()){
            int k = q.front();
            q.pop();
            if(check[k]==1) continue;
            vector<int> v = computers[k];
        
            for(int j=0; j<v.size(); j++){
                if(j==k) continue;
                if(v[j]==1){
                    q.push(j);
                }
            }
            check[k] = 1;
        }
    }
    return answer;
}

• 풀이
  총 몇개의 그래프 덩어리가 존재하는지 확인하는 문제였다.
  이론상으로는 어떻게 풀지 알았는데, 코드로 짜려니 뭔가 잘 안됐다.

queue를 이용해서 특정 노드를 시작점으로 도달가능한 모든 지점을 탐색하고 check 배열에 체크한다.
check가 안된 노드에서 시작할 경우에만 answer값을 업데이트 해준다.