백준 2606번. 바이러스
1. 문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
2. 입력
- 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
- 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
- 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
3. 출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
4. 풀이
- 컴퓨터의 연결 관계를
vector배열로 표시해주었다. - computers[i]의 값들은 i번째 컴퓨터와 연결된 컴퓨터 번호이다.
- 1번 컴퓨터에 연결된 컴퓨터를 모두 찾으면 된다.
- DFS로 풀었다.
- DFS로 도착한 컴퓨터 인덱스를 가져와 해당
boolean배열을True로 바꾸어주었다.
- DFS로 도착한 컴퓨터 인덱스를 가져와 해당
- DFS를 모두 마친후 1을 제외한 visited 배열의 true 값을 모두 찾았다.
루프를 2부터 돌려서 1은 아예 안 셌다.
5. 첫 코드에서 수정한 점
- 무방향 그래프이기 때문에 어느 한쪽이라도 연결되어 있으면 둘 다 연결해주었다.
- 이것 때문에 이것저것 좀 찾아봤는데... 마지막 루프에서 등호를 빼먹었다.
역시 코딩은 디테일이 생명이다.
편하게 컴퓨터 숫자 그대로 쓰겠다고 해놓고 등호 빼먹어서 틀렸다.
6. 소스
#include <iostream>
#include <vector>
using namespace std;
bool visited[101];
vector<int> computers[101];
int num_computers;
void dfs(int x) {
visited[x] = true;
for(int i = 0; i < computers[x].size(); i++){
int y = computers[x][i];
if(!visited[y]) dfs(y);
}
}
int main() {
cin >> num_computers;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int from, to;
cin >> from >> to;
computers[from].push_back(to);
computers[to].push_back(from); // 양방향 연결해준 곳
}
dfs(1);
int answer = 0;
for (int i=2; i<=num_computers; i++) // 등호 빼먹은 곳
if(visited[i]) answer++;
cout << answer << endl;
}7. 풀이 2 (➕ 21.09.15)
글을 수정 하던 중 분리 집합을 이용하면 좋을 것 같아서 풀이를 추가합니다.
- DFS 말고 분리 집합으로 풀어보았다.
- n개의 컴퓨터의 부모를 모두 자기 자신으로 초기화한다.
- 서로 연결하는 작업을 합집합으로 해준다.
- 합집합이 모두 끝난 후 2번 컴퓨터부터 부모가 1인 컴퓨터의 개수를 찾아 출력해주면 된다.
8. 소스 2
#include <iostream>
#include <algorithm>
using namespace std;
int parent[101];
int n, m;
int findParent(int x) {
if (x == parent[x]) return x;
else return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
int answer = 0;
for (int i = 2; i <= n; i++) {
if (findParent(i) == 1) answer++;
}
cout << answer;
}