백준 2606번, 바이러스

백준 2606번 c++ 문제풀이

문제:

백준 2606

풀이:

1. 벡터에 연결 정보 저장.
2. dfs로 1부터 탐색 시작.
3. dfs를 통해 방문하지 않은 컴퓨터의 개수 파악.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void dfs(int start, bool visit[], vector <int> v[]){ // 깊이 우선 탐색, stack 사용

visit[start] = true;
int size = v[start].size();
for(int i=0;i<size;i++){
    int k = v[start][i];
    if(!visit[k]){ //방문하지 않았다면
    dfs(k,visit,v);
    }
}
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int com, link;

cin >> com;
cin >> link;
vector<int> v[com+1];

for(int i=0;i<link;i++){
    int input1, input2;

    cin >> input1 >> input2;

    v[input1].push_back(input2);
    v[input2].push_back(input1);
}

bool visited[com+1] = {0,};

dfs(1, visited, v);

int count = 0;

for(int i = 2;i <= com;i++){
    if(!visited[i]){
    count++;
    }
}
int result = com - count - 1;
cout << result;

return 0;
}

감사합니다.