[백준 2606번 C++] 바이러스

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

---

이해하기

탐색 문제는 문제를 읽으면 탐색으로 풀어야하는지 다른 유형의 문제들보다 티가 나는 거 같다. 

또, 엄청난 응용이 있다기 보다는 DFS나 BFS를 어떤 구현방법(인접 행렬, 인접 리스트)을 적절히 사용하는 지가 포인트가 되는 것 같다. 

 

탐색에서 체크해야할 부분은 가장 처음 방향 그래프, 무방향 그래를 구분해야한다. 

이번 문제에서는 무방향 그래프로, 1번 노드가 속한 사이클에 총 몇 개의 노드가 있는지 구해야했다.

---

최종코드

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

vector<int> v[101];
int visited[101]={0,};
int count = 0; 

void dfs(int n){
	//dfs가 호출되는 총 개수를 count (1번 노드로부터 이어지는 노드들의 개수)
    count++;
    visited[n] = 1;
    
    for(int i=0; i<v[n].size(); i++) {
        int x = v[n][i];
        if(visited[x] == 0) dfs(x);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].push_back(b);
        //무방향 그래프이므로 두번 저장
        v[b].push_back(a);
    }
    
    //1번 노드에서 이어지는 노드들만 탐색
    dfs(1);
    
    cout << count-1 << "\n";
    return 0;
}