[백준] 2606번 바이러스

문제

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

풀이과정

처음에 문제를 보고 아 BFS나 DFS를 사용하면 되겠다 라고 생각했는데 밑에 알고리즘 분류에 플로이드-워샬 알고리즘이라고 적힌 것을 보고 플로이드-워샬 알고리즘에 대해 찾아보고 사용해보려고 했는데 너무 어려운 것 같다.

그리고 검색해보니 사람들도 주로 BFS, DFS를 이용하여 풀어서 DFS를 이용해서 풀었다.

DFS, BFS 에 대한 개념은 머리에 있는데 아직은 구현이 매끄럽게 되지 않는 것 같다.

소스코드

#include <iostream>
#include <queue>
 
using namespace std;
 
#define MAX 101 // 컴퓨터의 수는 최대 100개
int network[MAX][MAX]; 
int visited[MAX];
int num_cmptr, num_pair_cmptr;
int ans;
 
void DFS(int cur_vertex)
{
    visited[cur_vertex] = 1;
 
    for (int i = 1; i <= num_cmptr; i++)
    {
        // 방문했거나 또는 인접리스트가 없거나
        if (visited[i] == 1 || network[cur_vertex][i] == 0) continue;
        else DFS(i);
    }
}
int main()
{
    cin.sync_with_stdio(false);
 
    int cmptr1, cmptr2;
 
    cin >> num_cmptr; // 컴퓨터의 수
 
    cin >> num_pair_cmptr; // 컴퓨터 쌍의 수
 
    while (num_pair_cmptr--)
    {
        cin >> cmptr1 >> cmptr2;
 
        network[cmptr1][cmptr2] = 1; network[cmptr2][cmptr1] = 1;
    }
    
    DFS(1);
 
    for (int i = 2; i <= num_cmptr; i++) // 첫 번째 컴퓨터를 제외하고 방문한 컴퓨터 체크
    {
        if (visited[i] == 1) ans++;
    }
 
    cout << ans;
 
    return 0;
}