[프로그래머스][Lv.3][Cpp] 네트워크

1. 문제

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

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

 

2. 접근 방식

• 입력 받은 인접 행렬에 몇개의 그래프가 존재하는지를 묻는 문제
• BFS를 수행 후에도 방문하지 않은 노드가 남아 있다면 다른 그래프가 존재한다고 판단함 (방문하지 않은 노드가 없을 때까지 반복하여 탐색)
• 인접 행렬 형식의 2차원 Vector를 인접리스트 형식으로 변경 후 BFS 수행

 

3. 코드

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

using namespace std;

void bfs(int start, vector<int> *graph, bool* visited){
    queue<int> q;
    int nowNode;
    
    q.push(start);
    visited[start] = true;
    
    while(!q.empty()){
        nowNode = q.front();
        q.pop();
        
        for(auto node : graph[nowNode]){
            if(!visited[node]){
                q.push(node);
                visited[node] = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;

    vector<int> *computer = new vector<int>[n+1];
    
    for(int i=0; i < n; i++){
        for(int j=0; j < n; j++){
            if(computers[i][j] == 1 && i != j){
                computer[i+1].push_back(j+1);
            }
        }
    }
    
    
    bool *visited = new bool[n + 1];
    memset(visited, 0, sizeof(bool) * (n+1));

    for(int i=1; i<n+1; i++){
        if(!visited[i]){
            bfs(i, computer, visited);
            answer++;
        }
    }
    
    return answer;
}

 

4. 결과