99클럽 코테 스터디 31일차 TIL, 프로그래머스 / 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=cpp

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int groupCnt = 0;

vector<bool> visited;
bool dfs(int st, const vector<vector<int>>& computers)
{
    if (visited[st]) return false;
    visited[st] = true;
    const vector<int>& conn = computers[st];
    for (int nxtCom = 0; nxtCom < conn.size(); ++nxtCom)
    {
        if (conn[nxtCom] == 0) continue;
        dfs(nxtCom, computers);
    }
    return true;
}

int solution(int n, vector<vector<int>> computers) 
{
    // dfs 를 타고 들어가면서 찾은 대상들을 visited 체크한다.
    // 그리고 그룹의 개수로 판단한다.
    int answer = 0;
    visited.resize(n + 1);
    
    for (int com = 0; com < n; ++com)
    {
        if (dfs(com, computers)) groupCnt += 1;
    }

    return groupCnt;
}

 

각 컴퓨터를 시작점으로 하여 dfs 를 순회하면서 방문 처리를 한다.

만약 새롭게 방문된 적이 있다면 true 를 리턴하게 하고

groupCnt 를 증가. 이 groupCnt 는 하나의 네트워크 그룹을 의미