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

📝 네트워크

문제 설명

네트워크

해결 방법

그래프 순회(DFS, BFS)를 이용하여 해결 가능하다.
각각의 컴퓨터들을 그래프에서 하나의 정점이라고 생각한다.
그래프의 정점을 모두 방문하기 위해 필요한 최소 그래프 횟수를 카운트하면 그것이 네트워크의 총 개수일 것이다.
즉, 0부터 n - 1까지 정점 번호를 증가시키면서, 해당 정점을 아직 방문하지 않았다면 그래프 순회 알고리즘을 수행하고, 그 수행횟수를 카운트하여 반환한다.

💻소스코드

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);
    
    for (int i = 0; i < n; i++) {
        
        if (visited[i])		// 이미 검사한 컴퓨터면 넘어감
            continue;
        
        queue<int> q;
        q.push(i);
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            
            if (visited[v])
                continue;
            
            visited[v] = true;
            
            // 하나의 컴퓨터와 인접한 모든 컴퓨터들을 q에 삽입
            for (int j = 0; j < n; j++) {
                if (v != j && computers[v][j] == 1 && !visited[j])
                    q.push(j);
            }
        }
        
        answer++;	// BFS 순회 횟수 카운트
    }
    
    return answer;
}