백준 2606 바이러스 C++

문제설명

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1 복사

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1 복사

4

 

 

=> DFS 문제입니다. 

=> 주어진 정점과 간선들은 배열을 통해 구현해두어야합니다. 

=> arr[MAX][MAX] : 간선을 표현한 배열 => 각 정점이 연결되어 있을 경우 '1'로 표현하였습니다. 

=> 양방향 간선이므로 arr[1][3] = 1일 경우, arr [3][1] =1로 표현해 주어야합니다. 

=> check[MAX] 배열 : 해당 정점을 다녀왔는지 확인하는 배열입니다. 

 

=> 위 두가지를 참조하며 DFS를 이용해서(재귀) 1로 인해 탐색하게 되는 정점들의 개수를 세면 됩니다. 

=> 1로 인해 칠해지는 정점이므로, 1은 제외하여야합니다. 

=> 아래는 풀이할때 사용한 필기입니다. 

 

 

 

 

 

#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <utility>

#define MAX 102

using namespace std;

int M,N; //M : 정점갯수, N : 간선갯수
bool check[MAX];//갔다온지 확인하는 행렬
bool arr[MAX][MAX]; //인접행렬
vector<int> list[MAX]; //인접리스

int answer=0;

void dfs(int V, int vnumber) //시작점, 정점의 갯수
{
    check[V]=true;
    answer++;
    
    
    for(int i=1; i<=vnumber; i++)
    {
        if(arr[V][i] && !check[i])
        {
            dfs(i, vnumber);
        }
    }
}

int main()
{
    cin >> M >> N;
    
    for(int i=0; i<N; i++)
    {
        int from, to;
        cin >> from >> to;
        arr[from][to] = arr[to][from] = true;
    }
    
    dfs(1, M);
    
    cout << answer-1;
    return 0;
}