#문제
2606번: 바이러스
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
#접근방법
dfs를 사용하여 문제에 접근하였다.
반응형
#풀이
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> v[105];
int virus[105];
int ans;
void dfs(int x){
for(int i=0;i<v[x].size();i++){
int k = v[x][i];
if(virus[k]==0){
virus[k] = 1;
ans++;
dfs(k);
}
}
return;
}
int main(){
int n,m;
int a,b;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
virus[1] = 1;
dfs(1);
printf("%d",ans);
return 0;
}
이 문제는 그래프를 탐색하여 몇 개의 컴퓨터가 바이러스에 걸리는지 찾는 문제이다.
그래프 탐색 기법중 깊이우선탐색(dfs) 또는 너비우선탐색(bfs)중에서 dfs를 사용하여 풀어주었다.
n,m을 입력받고 반복문을 통해서 vector 자료구조에 그래프의 연결 정보를 입력해준다.
1번 컴퓨터가 감염이 됐으므로 virus[1] = 1을 넣고 dfs(1)을 호출시킨다.
v[x]에 들어있는 크기만큼 반복문을 돌리고 간단하게 정리하기위해 k변수에 v[x][i]를 넣어준다.
그리고 virus[k]==0이면 1번과 연결된 컴퓨터중 아직 감염이 안된 컴퓨터이므로 virus[k] = 1을 넣고 ans++를 하고 dfs(k)를 호출한다.
dfs로 1번과 연결된 컴퓨터를 한 번씩 다 탐색을 하면 dfs함수는 종료가 된다.
ans를 출력하면 정답이다.
#성능
#정리
그래프 탐색기법인 dfs나 bfs를 알고 있는 것,
이를 구현할 수 있는 구현력이 있으면 쉽게 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 9461번 : 파도반 수열 [C/C++] (0) | 2022.06.27 |
---|---|
[백준] 9375번 : 패션왕 신해빈 [C/C++] (1) | 2022.06.26 |
[백준] 2579번 : 계단 오르기 [C/C++] (0) | 2022.06.24 |
[백준] 17626번 : Four Squares [C/C++] (0) | 2022.06.23 |
[백준] 17219번 : 비밀번호 찾기 [C/C++] (0) | 2022.06.22 |