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

2606번: 바이러스 (acmicpc.net)

문제 해석

• 감염된 컴퓨터를 배열로 표현하고 그 수를 출력한다

알고리즘 분류

• dfs(깊이우선탐색)

풀이

• 컴퓨터 간 연결 관계를 그래프로 나타낸다
• dfs를 이용해 감연된 컴퓨터를 표시한다
• 감염된 컴퓨터 수를 출력한다

코드

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

int n, s, count = 0;
vector<int> visited;
vector<vector<int>> arr;

void dfs(int start) {
  for (int i = 1; i <= n; i++) {
    if (arr[start][i] == 1 && visited[i] == 0) {
      visited[i] = 1;
      dfs(i);
      count++;
    }
  }
}

int main() { 
  cin >> n >> s;

  arr.resize(n + 1, vector<int>(n + 1, 0));
  visited.resize(n + 1, 0);
  visited[1] = 1;
  for (int i = 0; i < s; i++) {
    int x, y;
    cin >> x >> y;
    arr[x][y] = 1;
    arr[y][x] = 1;
  }

  dfs(1);
  cout << count;
}