[프로그래머스]깊이/너비 우선 탐색(DFS/BFS) : 네트워크 (level 3)(c++)

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

코딩테스트 연습 - 네트워크

 

#include <string>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> &computers, vector<bool> &check, int node, int n)
{
    for (int i = 0; i < n; ++i)
    {
        // 현재 노드와 연결되어 있고 아직 방문안한 노드라면 dfs함수 재귀호출 
        if (computers[node][i] == 1 && !check[i])
        {
            check[i] = true;
            dfs(computers, check, i, n);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {

    vector<bool> check(n);
    int network = 0;
    
    // 아직 방문안한 노드에서부터 인접행렬을 dfs탐색
    for (int i = 0; i < n; ++i)
    {
        if (!check[i])
        {
            check[i] = true;
            dfs(computers, check, i, n);
            // 하나의 그래프가 끝나면 카운팅
            ++network;
        }
    }

    return network;
}

 

 

그래프, 인접 행렬 배경지식이 있다면 풀수 있는 간단한 문제이다.

프로그래머스에선 레벨 3로 분류되어있지만 BOJ에서라면 브론즈1~2?쯤 되는 것 같다.