프로그래머스 - 네트워크

고득점kit - 네트워크

간단하게 그래프의 연결요소 개수 구하기 문제.
dfs 함수 구현하고, 모든 노드에서 탐색하면서 중간에 중지 되는 부분 생기면 개수 더한다.

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

bool visited[201];

void dfs(int cur, vector<vector<int>> adj)
{
    visited[cur] = true;
    for (auto next : adj[cur])
    {
        if (!visited[next])
            dfs(next, adj);
    }
}

int dfsForComponents(int n, vector<vector<int>> adj)
{
    memset(visited, 0, sizeof(visited));
    int components = 0;
    for (int i = 0; i < n; i++) //처음부터 끝까지 모든 노드
    {
        if (!visited[i])
        {
            dfs(i, adj);
            components++; //여기로 오면 중간에 끊겼다는 뜻
        }
    }
    return components;
}

int solution(int n, vector<vector<int>> computers)
{
    vector<vector<int>> adj;	//탐색 위해 인접행렬 만든다
    adj.resize(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                continue;
            if (computers[i][j])
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    cout << dfsForComponents(n, adj);
}