C++:: 프로그래머스 < 네트워크 >

그래프 문제에서 bfs를 활용하여 푼 문제이다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

map<int, vector<int>> um;

int solution(int n, vector<vector<int>> computers) {    
    vector<int> vis(n);
    for (int i=0; i<n; i++) {// 각 인덱스로 방문배열 초기화
        vis[i] = i;
    }
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) { // 노드끼리의 간선 저장
            if (!computers[i][j]) continue;
            um[i].push_back(j);
            um[j].push_back(i);
        }
    }
    
    for (auto& node : um) {
        queue<int> q;
        sort(node.second.begin(), node.second.end());// 미리 정렬
        for (auto& line : node.second) {// 연결된 노드들 추가
            q.push(line);
        }
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (vis[cur] != cur) continue;// 방문한적 있다면 넘긴다.
            vis[cur] = min(vis[cur], vis[node.first]);// 네트워크에사 가장 작은 노드로 방문배열에 저장
            for (auto& next : um[cur]) {// 방문하지 않았다면 연결된 노드 추가
                if (vis[next] != next) continue;
                q.push(next);
            }
        }
    }
    
    sort(vis.begin(), vis.end());
    vis.erase(unique(vis.begin(), vis.end()), vis.end());// 중복 삭제
    return vis.size();
}

다른 간단한 dfs 풀이도 참조한다.

#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);

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

        // visit node and start DFS
        network++;
        visited[i] = 1;

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

    return network;
}