[Algorithm] 프로그래머스 C++ : 네트워크

 

 

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

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

 

그래프의 개수를 구하는 문제

 

평소 하던대로 dfs를 돌리고

 

dfs가 한번 다 돌아갈때마다 그래프가 1개이기 때문에

 

그때마다 answer를 +1 해준다

 

 

Code

#include <string>
#include <vector>

using namespace std;

int check[200];

void dfs(int x, int n, vector<vector<int>> computers) {
    check[x] = 1;
    
    for(int i=0; i<n; i++) {
        if(check[i] == 0 && computers[x][i] == 1) {
            dfs(i, n, computers);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0; i<n; i++) {
        if(check[i] == 0) {
            dfs(i, n, computers);
            answer++;
        }
    }
    
    return answer;
}