PGMRS : 네트워크 - DFS

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void DFS(int from, int n, vector<int> &visited, vector<vector<int>> &computers) {

    for (int i = 0; i < n; i++) {
        if (from != i && computers[from][i] == 1 && visited[i] == 0) {
            visited[i] = 1;
            DFS(i, n, visited, computers);
        }
    }
}
int solution(int n, vector<vector<int>> computers) {

    int network = 0;
    vector<int> visited(n, 0); // 크기가 n인 벡터 0으로 초기화

    for (int i = 0; i < n; i++) {
        if (visited[i] == 1) {
            continue;
        }
        network++;
        visited[i] = 1;

        DFS(i, n, visited, computers);
    }

    return network;
}

• solution 함수에서 방문되지 않은 노드에 대해 network++을 하면서 computers[i]가 0인 외톨이 노드도 함께 카운팅된다.
• visited, computers 벡터에 대해 참조자를 넘기면서 메모리 절약 및 시간을 단축할 수 있다.
• DFS()에서, ...
  • from != i 여야 자기 자신 노드 방문을 피할 수 있음
• from과 i의 쓰임새 및 쓰는 순서 잘 파악하기
• visited는 1차원으로 선언한다!