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

#문제

2606번: 바이러스

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

2606번: 바이러스

 

---

#접근방법

dfs를 사용하여 문제에 접근하였다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> v[105];
int virus[105];
int ans;

void dfs(int x){
    for(int i=0;i<v[x].size();i++){
        int k = v[x][i];

        if(virus[k]==0){
            virus[k] = 1;
            ans++;
            dfs(k);
        }
    }

    return;
}

int main(){
    int n,m;
    int a,b;

    scanf("%d %d",&n,&m);

    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);

        v[a].push_back(b);
        v[b].push_back(a);
    }

    virus[1] = 1;
    dfs(1);

    printf("%d",ans);

    return 0;
}

 

이 문제는 그래프를 탐색하여 몇 개의 컴퓨터가 바이러스에 걸리는지 찾는 문제이다.

 

그래프 탐색 기법중 깊이우선탐색(dfs) 또는 너비우선탐색(bfs)중에서 dfs를 사용하여 풀어주었다.

 

n,m을 입력받고 반복문을 통해서 vector 자료구조에 그래프의 연결 정보를 입력해준다.

 

1번 컴퓨터가 감염이 됐으므로 virus[1] = 1을 넣고 dfs(1)을 호출시킨다.

 

v[x]에 들어있는 크기만큼 반복문을 돌리고 간단하게 정리하기위해 k변수에 v[x][i]를 넣어준다.

 

그리고 virus[k]==0이면 1번과 연결된 컴퓨터중 아직 감염이 안된 컴퓨터이므로 virus[k] = 1을 넣고 ans++를 하고 dfs(k)를 호출한다.

 

dfs로 1번과 연결된 컴퓨터를 한 번씩 다 탐색을 하면 dfs함수는 종료가 된다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

그래프 탐색기법인 dfs나 bfs를 알고 있는 것,

 

이를 구현할 수 있는 구현력이 있으면 쉽게 풀 수 있는 문제였다.