https://www.acmicpc.net/problem/2606
BFS를 활용하면 금방 풀리는 문제이다. 입력으로 주어지는 그래프를 인접 리스트 형식으로 구현해놓고, BFS만 돌리면 끝이다. 다만 여기서 포인트는 BFS를 순회하면서 정점들을 기록하는것이 아닌 정점들의 갯수만 카운트 시키고, 마지막 출력할때에 카운트된 변수에서 1만 빼주면 된다. 문제에서 요구하는 출력 조건이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"이기 때문에 1번 컴퓨터 본인은 제외하고 카운트 해야 하기 때문이다. BFS만 알고있다면 누구나 금방 풀수있는 문제이다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visited[105];
vector<int> Graph[105];
int cnt = 0;
void BFS(int start) {
queue<int> Q;
Q.push(start);
visited[start] = true;
while(!Q.empty()) {
int n = Q.front();
Q.pop();
cnt++;
for (int i=0; i<Graph[n].size(); i++) {
int idx = Graph[n][i];
if (!visited[idx]) {
Q.push(idx);
visited[idx] = true;
}
}
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int V, E;
cin >> V >> E;
while(E-->0) {
int x,y;
cin >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
BFS(1);
cout << cnt-1 << '\n';
return 0;
}
728x90
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] #2667 단지번호붙이기 (0) | 2024.01.10 |
---|---|
[BOJ] #1697 숨바꼭질 (0) | 2024.01.10 |
[BOJ] #1260 DFS와 BFS (0) | 2024.01.06 |
[BOJ] #5639 이진 검색 트리 (0) | 2024.01.05 |
[BOJ] #1991 트리 순회 (0) | 2024.01.05 |