백준 2606 바이러스 / C++

문제 : 2606

풀이 point

자료구조 그래프를 활용하여 그래프를 구하고 1에서 뻣어나가는 모든 컴퓨터를 방문한다.
방문 하였을 때의 visit배열의 차이점을 통해 방문한 컴퓨터의 갯수를 확인한다.

풀이 방법

그래프를 구현 및 탐색한다. dfs를 활용하였다.

코드

//백준 2606, 바이러스

#include <iostream>
#include <vector>

std::vector<int> graph[101];
int visit[101];

void dfs(int i){
    if(visit[i]) return; //조기 종료 
    visit[i] = 1;
    for(auto n : graph[i]){
        if(visit[n]) continue;
        dfs(n);
    }
}

int main (){
    int N, M; //컴퓨터 수, 간선 수
    std::cin >> N >> M;
    for(int i{0}; i<M; ++i){
        int a, b;
        std::cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(1);
    int sum{0};
    for(int i{1}; i<=N; ++i){
        sum += visit[i];
    }

    std::cout << sum-1;

    return 0;
}