[백준 2606] 바이러스

문제 링크 : https://www.acmicpc.net/problem/2606

2606번: 바이러스

1번부터 dfs를 돌며 탐색한 노드의 수를 세는 문제이다

---

#include<cstdio>

// 인접행렬
int map[101][101] = { 0 };
// 노드를 방문했는지 저장하는 visit 배열
int visit[101] = { 0 };
int computer_num, ans = 0;

// 감염된 사람을 전부 찾아내는 dfs
void dfs(int n)
{
    ans++;  // dfs 한번 돌때마다 새로운 사람이 감염된다는 것
    visit[n] = 1;   // 방문했으므로 1
    for (int i = 1; i <= computer_num; i++) // 모든 노드중에
    {
        if (map[n][i] && !visit[i]) dfs(i);  // 이동가능하고 방문한적 없으면 탐색
    }
}

int main()
{
    int n;
    int x, y;
    scanf("%d %d", &computer_num, &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        map[x][y] = map[y][x] = 1;  // 양방향 그래프
    }

    // 바이러스는 1번부터 시작
    dfs(1);

    // 1번은 바이러스 걸린 사람에서 제외해야되므로
    // ans - 1 을 출력
    printf("%d", ans - 1);  

    return 0;
}