[PG] 네트워크 [C++]

 

프로그래머스

 

 

DFS로 하나의 네트워크에 속하는 컴퓨터를 모두 방문할 수 있으니, DFS를 수행한 횟수가 정답이 된다

 

 

코드

#include <string>
#include <vector>

using namespace std;

bool visited[201];
vector<int> graph[201];

void dfs(int cur) {
    for (int next : graph[cur]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = true;
        dfs(next);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < computers.size(); i++) {
        for (int j = 0; j < computers[i].size(); j++) {
            if (computers[i][j] == 1 && i != j) {
                graph[i].push_back(j);
            }
        }
    }
    
    for (int i = 0; i < computers.size(); i++) {
        if (!visited[i]) {
            answer++;
            visited[i] = true;
            dfs(i);
        }
    }
    
    return answer;
}