프로그래머스 (네트워크, 깊이/너비 우선 탐색(DFS/BFS)) C++

 

초반에 문제 Setting 할 때 시간이 많이 걸렸고 묶인 것이 몇 개인지 파악하는 것에서도 많이 시간을 썼다. 하다보니까 visited 하지 않은 것을 시작할 때가 네트워크가 달라지는 순간이었다. 

 

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<vector<int>> adj(n+1);
    vector<int> visited(n+1, 0);
    queue<int> queue;
    
    // Diagonal Matrix 이므로 Upper에 해당하는 것만 취해서 adjacent list 만들기
    for(int i = 0 ; i < n ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            if(computers[i][j] == 1) {
                adj[i+1].push_back(j+1);
                adj[j+1].push_back(i+1);
            }
        }
    }
    
    // BFS를 이용해서 visited 하지 않은 사이클을 돌 때마다 answer 를 증가시킨다.
    for(int i =1 ; i <= n ; i++) {
        if(visited[i] == 1) continue;
        queue.push(i);
        visited[i] = 1;
        
        while(!queue.empty()) {
            int node = queue.front();
            queue.pop();
            
            for(int j = 0 ; j < adj[node].size() ; j++) {
                if(!visited[adj[node][j]]) {
                    visited[adj[node][j]] = 1;
                    queue.push(adj[node][j]);
                }
            }
        }
        answer++;
    }
    
    return answer;
}