프로그래머스 네트워크 c++

 

dfs로 풀 수 있는 문제이다. 결국 n개의 컴퓨터가 존재하는거니까 컴퓨터가 방문되지 않았다면 그 컴퓨터부터 연결된 모든 컴퓨터들을 방문하고 (dfs 수행) visited 배열에 방문 기록을 업데이트 해준다.

그리고 다시 n개의 컴퓨터에 대해서 방문하지 않았다면 그 컴퓨터부터 네트워크에 속하는 컴퓨터들을 탐색해준다. 

 

그리고 이렇게 방문한 n개의 컴퓨터 개수가 네트워크 개수가 된다.

#include <string>
#include <vector>

using namespace std;

int N;
int visited[201];
vector<vector<int>> connected;

void dfs(int x){
    for (int i=0;i<N;i++){
        if (connected[x][i]==1 && !visited[i]){
            visited[i]=1;
            dfs(i);
        }
    }
}

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