[프로그래머스] (DFS/BFS) 네트워크 c++

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

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

프로그래머스 네트워크문제

BFS 를 이용.

 

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int visit[n]; //방문정점
    vector <int> mycom[n]; //벡터 배열을 이용한 트리 구현
    queue<int> q;
    
    for(int i=0; i<n; i++) //방문 정점배열 초기화
    {
        visit[i]=0;
    }
    
    
    for(int i=0; i<n; i++) //mycom 초기화
    {
        for(int j=0; j<n; j++)
        {
            if(i==j) continue;
            if(computers[i][j]==1)
            {
                mycom[i].push_back(j);
            }
        }
    }
    
    
    int start;
    for(int i=0; i<n; i++) //BFS시작
    {   
        if(visit[i]==1) 
        {
            continue;
        }

        start=i;
        while(1) 
        {
            visit[start]=1;
            for(int j=0; j<mycom[start].size(); j++)
            {
                if(visit[mycom[start][j]]==1) continue;
                q.push(mycom[start][j]);
            }
            
            if(q.empty()) break;
            
            start=q.front();
            q.pop();
        }
        answer++; //네트워크 수
    }
    
    
    return answer;
}