[백준] 2606 - 바이러스, C++ (알고리즘 정리 예정)

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

2606번: 바이러스

 본 문제는 '2004 한국정보올림피아드 지역본선 초등부 3번 문제'로 문제 분류는 '플로이드 와샬 알고리즘'이라고 되어 있는데 BFS로 풀린다. 최단 경로 알고리즘(정리 예정) 코딩 절차는 다음과 같다.

1. 간선 정보 입력
2. 정점 1에서 시작
3. 감염된 컴퓨터 개수 파악

#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
int main() {
    bool chk[101];
    int n, m, x, y;
    scanf("%d %d", &n, &m);
    vector<int> v[101];
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    int cnt = 0;
    chk[1] = true;
    // 감염된 컴퓨터 찾기
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        cnt += 1;
        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i];
            if (!chk[next]) {
                chk[next] = true;
                q.push(next);
            }
        }
    }
    cnt -= 1; // 시작점 제외
    printf("%d", cnt);
    return 0;
}