https://www.acmicpc.net/problem/2606
문제
> 신종 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 걸리면 네트워크상 연결된 컴퓨터가 모두 감염된다.
> 그림처럼 컴퓨터가 연결되어있으면 1번이 감염됐을 때, 2,5번이 감염되고, 3,6번 또한 감염된다. 하지만 4,7번은 네트워크공유를 안하므로 안걸린다.
컴퓨터의 수와 네트워크상 연결된 관계가 주어질 때, 1번 컴퓨터를 통해 감염되는 컴퓨터의 수를 구해라.접근
문제의 흐름을 보면 DFS와 BFS를 쓰는 그래프 탐색 문제를 적용하는 문제이다. 컴퓨터들은 노드고 네트워크는 간선이다. 이를 구현해 탐색해 연결된 컴퓨터의 수를 구한다.
문제해결
> BFS로 해결하기 위해 BFS를 구현해준다. 큐를 생성하고 매개변수로 들어온 start인 1번 피씨가 들어온다.
> 큐가 빌 때까지 반복을 해주며, 연결된 피씨를 찾기위해 큐의 맨앞의 값(현재 탐색해야하는 값)을 복사해 가져오고 제거한다.
> 만약 그 피씨가 이미 감염검사를 했으면 다음 피씨로 넘어간다. 안했다면 감염된 피씨의 수에 추가하고, 검사했다고 표시한다.(visited = true)
> 해당 피씨와 네트워크상 연결된 피씨를 찾기 위해 해당 피씨와 연결된 피씨를 p로 가져온뒤 검사여부를 조건으로 따져 안했으면 다음 탐색 대상으로 큐에 넣는다. 위 과정을 반복한다.
> 검사가 끝나고 큐가 비면 끝난다. 끝나면서 감염된 피씨의 수를 출력한다. 여기서 1번피씨는 제외하고 추가 감염된 피씨의 수이기 때문에 1을 빼준다.
> main함수에선 입력으로 주어진 피씨 수, 네트워크상 연결된 쌍의 수를 입력받고, 쌍을 입력받는다. 네트워크는 양방향이므로 양방향 간선을 입력받아줄 때 처럼 한다.
> 1번피씨와 연결된 피씨부터 차례로 검사하기위해 정렬해주고 BFS함수에 1번 피씨를 넣어 연산한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> pc;
vector<bool> visited;
int cnt = 0;
void BFS(int start)
{
queue<int> q;
q.push(start);
while (!q.empty())
{
int i = q.front();
q.pop();
if (visited[i]) continue;
cnt++;
visited[i] = true;
for (auto p : pc[i])
{
if (!visited[p])
{
q.push(p);
}
}
}
cout << cnt-1 << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
pc.assign(N+1, vector<int>());
visited.assign(N+1, false);
for (int i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
pc[a].push_back(b);
pc[b].push_back(a);
}
for (int i = 1; i <= N; i++) sort(pc[i].begin(), pc[i].end());
BFS(1);
}
후기
스토리가 장황하지만 기본적인 BFS, DFS 문제라 할만했다. 다음엔 아직 익숙치않은 DFS로 풀어보자
