[C++] 백준 2606 : 바이러스
#include <iostream>
#include <queue> // bfs
using namespace std;
int V, E; // vertex, edge
int map[101][101] = {0}; // 간선 저장
bool visited[101] = {false}; // 방문 여부
queue<int> q;
int cnt = 0; // 바이러스에 걸린 컴퓨터 수
void BFS(int n){
if(!visited[n]){
visited[n] = true; // 방문 체크
}
q.push(n); // 큐에 첫번째 노드 넣기
while(!q.empty()){
int vertex = q.front(); q.pop();
for(int i=1; i<=V; i++){
if(map[vertex][i] == 1 && !visited[i]){ // 간선 연결되어있고 방문되지 않았을 경우
visited[i] = true; // 연결된 노드 방문
q.push(i); // 노드 큐에 넣기
cnt++; // 감염된 컴퓨터 개수 세기
}
}
}
}
int main(int argc, char **argv){
scanf("%d %d",&V,&E);
int a, b;
for(int i=1; i<=E; i++){
scanf("%d %d",&a,&b);
map[a][b] = 1;
map[b][a] = 1; // 간선 연결, 방향 없음
}
BFS(1); // 1번 컴퓨터 감염 확인
printf("%d", cnt);
return 0;
}
BFS 연습용 문제.
인터넷 검색 없이 내 힘으로 풀 수 있었다 만세!!
BFS를 하면 간선이 연결되어있는 모든 노드를 검색한다. 1번 컴퓨터가 감염되었으므로 노드 1에서 BFS를 실행하면 된다. 그러면 1번 컴퓨터와 연결되어있는 모든 컴퓨터를 너비 우선 탐색으로 풀 수 있다(DFS도 가능)
만약에 간선이 연결되어있지 않으면 감염되지 않으므로 다른 노드들은 검사하지 않아도 된다. 연결된 노드의 수를 세면 된다.
Author And Source
이 문제에 관하여([C++] 백준 2606 : 바이러스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-2606-바이러스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)