백준 2606번: 바이러스

문제

문제 바로가기> 백준 2606번: 바이러스

풀이

깊이 우선 탐색(dfs)을 이용하여 문제를 풀었다. 처음에 dfs(1)을 호출할 때 ans++은 답에 포함되지 않아야하므로 마지막에 ans-1을 정답으로 출력해주었다.

#include <iostream>
using namespace std;

int network[101][101] = {};
int visit[101] = {};
int computerNum, ans=0;

void dfs(int n){
    ans++;
    visit[n]=1;
    for(int i=1; i<computerNum+1; i++){
        if(network[n][i] && !visit[i]) dfs(i);
    }

}

int main(){
    int pairNum, a, b;
    cin >> computerNum;
    cin >> pairNum;
    for(int i=0; i<pairNum; i++){
        cin >> a >> b;
        network[a][b]=1; network[b][a]=1;
    }
    dfs(1);
    cout << ans-1;
}