백준) 2606 바이러스

2606. 바이러스

https://www.acmicpc.net/problem/2606

1. 접근

1번이 연결된 그래프의 노드수를 구하는 문제다.

인접리스트로 구성한 맵에 대해 1번 노드를 DFS / BFS 하면 되겟다.

DFS()로 풀어보자.

2. 풀이

DFS()는 재귀적으로 X에 연결된 노드가 몆개인지 알려다 줘야 한다.

DFS(1)이 DFS(2)를 불렀고, 최종적으로는 DFS(1)에게 DFS(2)에서 얼마나 진행되는지 알려줘야 하는 것이다.

3. 코드

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, m, a, b;
int visit[101];
vector<vector<int>> map;
 
int dfs(int x) {
    int cnt = 1;
    visit[x] = 1;
 
    for (auto next : map[x]) {
        if (visit[next])
            continue;
 
        cnt += dfs(next);
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &n, &m);
    map.resize(n + 1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        map[a].push_back(b);
        map[b].push_back(a);
    }
 
    printf("%d", dfs(1) - 1);
 
    return 0;
}