C++ / 2606/ 바이러스 ( 깊이 우선 탐색 )

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

문제 요약

한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 됩니다.

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성해야합니다.

문제 풀이

1. 컴퓨터의 수와 간선의 수를 입력 받습니다.
2. 탐색할 트리를 입력받습니다.

3. 아래 예제를 입력받으면 v에는 이렇게 저장됩니다.

v[1] = {2, 5}
v[2] = {1, 3, 5}
v[3] = {2}
v[4] = {7}
v[5] = {1, 2, 6}
v[6] = {5}
v[7] = {4}

4. dfs  함수를 만듭니다.

5. 1을 매개변수로 넣어줘서 1과 연결되어 있는 노드들을 탐색합니다.

6. cnt로 방문 횟 수를 카운트합 니다.

7. cnt를 출력합니다.

주의할 점

이 문제는 깊이 우선 탐색 ( dfs ) 를 사용하여 풀어야 하는 문제입니다.
깊이 우선 탐색 ( dfs )은 루트 한 쪽으로 탐색 할 수 있는 만큼 탐색한 후 다시 돌아가 다른 루트를 탐색하는 방법입니다.
모든 연결되어 있는 루트를 탐색 할 때 사용합니다.

코드

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

bool visited[101];
vector<int> v[101];
int cnt = 0;
int n, m;

void dfs(int x) {
    cnt++;
    visited[x] = true;
    for (int i : v[x]) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(1);
    cout << cnt - 1;
}

반응형

예제

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

결과