[프로그래머스] 네트워크 C++

예제 1)

예제 2)

---

그래프에서 몇 개의 '그룹'이 있는지 세면 되는 문제다.

1. 1번 노드부터 n번 노드까지 반복문을 돌며 아직 방문(visited[])하지 않은 노드라면 dfs/bfs로 탐색해준다.
2. 탐색을 시작한 노드와 연결된 모든 노드들은 방문한 것으로 처리되며, 연결된 노드들은 하나의 그룹으로 취급할 수 있다.
   • 탐색을 할때마다 하나의 그룹을 찾은 것이다.
3. 그룹의 갯수를 세어 반환한다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

void bfs(vector<vector<int>> &computers, bool visited[], int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty())
    {
        int here = q.front();
        q.pop();
        
        for (int i = 0; i < computers[here].size(); ++i)
        {
            if (visited[i] || !computers[here][i])
                continue;
            
            visited[i] = true;
            q.push(i);
        }
    }
}

int solution(int n, vector<vector<int>> computers)
{
    int ans = 0;
    bool visited[n];
    memset(visited, false, sizeof(visited));
    
    for (int i = 0; i < n; ++i)
    {
        if (!visited[i])
        {
            bfs(computers, visited, i);
            ++ans;
        }
    }
    
    return ans;
}

---

DFS나 BFS 같이 그래프를 탐색하는 법을 안다면 쉽게 응용하여 풀 수 있는 문제이다. 특히 DFS/BFS는 응용하여 폭 넓게 사용할 수 있기 때문에 숙지하는 것이 좋다.