[Programmers] 네트워크 (C++)

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

프로그래머스

걸린 시간 : 8분 50초

---

알고리즘

간단한 BFS 혹은 DFS 문제이다.

이 문제는 어떤 것으로 풀어도 나쁘지 않지만, 코드 구현은 BFS보다 재귀를 사용하는 DFS가 간단한다.

방문체크는 vis라는 배열로 처리하고, 방문하지 않은 노드를 발견하면 카운트를 하고 DFS를 실행하면 끝이다.

정답 코드

#include <string>
#include <vector>

using namespace std;

bool vis[201];

void dfs(int i, vector<vector<int>>& computers) {
    vis[i] = true;
    for (int j = 0; j < computers.size(); j++) {
        if (!vis[j] && computers[i][j]) {
            dfs(j, computers);
        }
    }
}

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