BOJ 2606: 바이러스

✔ 문제 링크

---

BOJ 2606: 바이러스

---

✔ 문제해결전략

• 그래프 탐색
• BFS(Breadth First Search)
• Flood fill

---

✔ 해결과정

• 1번 컴퓨터를 시작점으로 정직하게 BFS 하면 된다.
• 이 문제에서의 경우 컴퓨터 네트워크를 vector<vector>를 활용하여 adjacency list 방식으로 표현하는 것이 편해 보여서 그렇게 하였다.

---

✔ 정답 Code

#include <bits/stdc++.h>

using namespace std;

vector < vector < int >> mp;
int vis[101];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, line;
    cin >> n;
    mp.resize(n + 1);
	cin >> line;

    while (line--) {
        int x, y;
        cin >> x >> y;
        mp[x].push_back(y);
		mp[y].push_back(x);
    }

    queue < int > q;
    int cnt = 0;

    vis[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int k: mp[cur]) {
            if (vis[k] != 0) {
				continue;
			}
            cnt++;
            vis[k] = 1;
            q.push(k);
        }
    }
	cout << cnt;
}

---

✔ Check Point

• vector<vector>를 활용하여 adjacency list 방식으로 그래프를 표현할 때 무방향 그래프는 간선에 연결된 두 노드의 adjacency list에 각각 상대방을 추가해야 한다는 것 주의하자(한쪽만 하면 안 된다)