🖊️ 문제

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

---

어제 풀었던 바이러스 와 문제가 비슷해서 놀랐다
사실.. 그냥 변수명과 그런게 비슷할 뿐 ..

모든 노드 방문해봐야 한다는 점,
최단거리를 구하는게 아니라는 점에서 DFS를 이용해서 풀었다.

다만, 연결된 네트워크의 수를 구하는 알고리즘은 생각을 해봐야 했다.
시작 노드를 기점으로 연결된 모든 노드를 DFS를 통해 찾는다.
그러면, 연결된 모든 노드를 다 돌아야 DFS가 종료된다.
-> 한 개의 DFS == 1개의 네트워크
그래서, 한 번의 DFS를 시작할 때 (solution에서 DFS 시작) answer++했다.

처음에는 connection의 개수를 세보려고 했는데,
그건 아니었다 ~
레벨3라서 겁먹었는데 생각보다 금방 풀었고, 괜찮았던 문제쓰~

🖊️ 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool visited[201] {false};

void dfs(vector<vector<int>>& com, int n, int cur)
{
    visited[cur] = true;
    
    for(int i = 0 ; i < n ; i++) {
        if (!visited[i] && com[cur][i] == 1) {
            dfs(com, n, i);
        }
    }    
}

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