[Olympiad] 지역본선 2004 초등부 : 바이러스 #2606

문제 링크

바이러스

문제 요약

• 첫째 줄에는 컴퓨터의 수가 주어진다.
• 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
• 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
• 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
• 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

플로이드 와샬 알고리즘

• 플로이드 와샬 알고리즘을 사용하여 1번 컴퓨터에 연결되어 있는 컴퓨터의 개수를 출력하면 된다.

문제 해답

#include <iostream>
using namespace std;
const int N_MAX = 100 + 1;
bool check[N_MAX][N_MAX];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    int p, q;
    int sum = -1;
    cin >> N >> M;
    for (int i = 0;i < M;i++) {
        cin >> p >> q;
        check[p][q] = true;
        check[q][p] = true;
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                if (check[i][k] && check[k][j]) check[i][j] = 1;

    for (int i = 1;i <= N;i++) {
        if (check[1][i])sum += 1;
    }
    cout << sum << endl;
}