[C++/2606] 바이러스 - using BFS

문제

그래프가 주어질 때 0번 노드와 몇개의 서로 다른 노드가 연결되어 있는지 반환하는 문제이다. 쉬움

아주 간단하게 BFS를 바로 쓸 수 있다. 노드에 대해서 for문 돌지 않고 바로 0번 노드 한번만 BFS를 돌면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    // N(컴퓨터 수), M(edge 수)
    int N, M, result = 0;
    cin>>N>>M;
    
    vector<vector<int>> v(N, vector<int>(N, 0));// 그래프 생성
    vector<bool> visited(N, false);		// 방문 기록
    
    for(int i = 0;i < M;i++)
    {
        int x, y;
        cin>>x>>y;
        
        // 0번 부터 M-1번으로 변경
        // 양방향 그래프를 만들어준다.
        v[x - 1][y - 1] = 1;
        v[y - 1][x - 1] = 1;
    }
    
    // BFS를 위한 queue 생성
    queue<int> q;
    
    // 0번 노드에 대해서 시작함
    q.push(0);
    visited[0] = true;
    
    while(!q.empty())
    {
        int temp = q.front();
        q.pop();
        
        // node에 연결된 정점을 모두 확인
        for(int i = 0;i < v[temp].size();i++)
        {
        	// 방문하지 않았고, 연결되어 있다면 방문처리하고 결과+1 한 다음 queue에 넣어서
            // 다시 연결된 node를 방문할 수 있도록 한다.
            if (v[temp][i] == 1 && visited[i] == false)
            {
                result++;
                visited[i] = true;
                q.push(i);
            }
            else
                continue;
        }
    
    }
    cout<<result;
    
    return 0;
    
}