[백준/C++] 2606번. 바이러스

백준 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를 모두 마친후 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;
}