2606. 바이러스

2606 바이러스

https://www.acmicpc.net/problem/2606

같은 네트워크에 연결된 컴퓨터 개수는 몇대인지 찾는 문제

---

문제 풀이

필요한 변수들

• 첫째 줄에는 컴퓨터의 수가 주어진다
  • 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. -> 컴퓨터의 수 (1<= int N <= 100)
• 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다 (쌍의 수를 입력받을 int M)
• 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다 -> M번만큼 출발지와 도착지를 받아야함 int start, int end
• 연결 노드를 저장한 **연결 리스트 vector< vector<int> > map; ** (2중 벡터를 이용)
• 감염된 컴퓨터의 개수를 표시할 int cnt
• DFS, BFS 이용시, 방문한 노드를 표현하기 위한 int visited[101] 배열

접근법

1. 연결리스트에 연결 관계를 입력받는다
   • 주의! 단방향 그래프가 아님!!!
   • 같은 네트워크에 속한다면 어느 방향이든 상관없이 바이러스에 걸릴 수있음 -> 연결 리스트에 추가시, start -> end 방향과 end -> start 방향 두가지 모두 추가해줘야함
2. 1번 노드부터 시작하여 같은 네트워크에 속한 노드의 개수를 체크한다
   • DFS방법, BFS방법 모두 가능함

• 1번 노드가 ‘감염시킨’ 컴퓨터의 개수이므로, 자기자신은 제외해야함. 마지막에 cnt-1 해줄 것!

DFS 방법

재귀적 호출을 이용한 DFS 이용

1. 1번 노드를 방문표시한다
2. cnt를 1 증가시킨다
3. 1번 노드와 연결된 다른 노드가 있는지 체크한다
	3-1. 있다면 그 노드가 방문 표시가 되어있는지 확인한다
		3-1-1. 방문 표시가 이미 되어있다면 패스한다
	3-2. 방문표시가 안되어 있다면 방문 표시를 하고 그 노드로 넘어간다
	1~3을 반복한다. 

BFS 방법

큐를 이용한 BFS

1. 큐를 생성
2. 큐에 1번 노드를 넣는다
3. 큐에서 맨 앞의 노드를 뺀다
4. 맨 앞의 노드의 연결된 다른 노드가 있는지 체크한다
	4-1. 있다면 그 노드가 방문 표시가 되어있는지 확인한다
		4-1-1. 방문 표시가 이미 되어있다면 패스한다
	4-2. 방문표시가 안되어 있다면 방문 표시를 하고 그 노드로 넘어간다

소스코드

DFS 풀이

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector< vector<int> > map;
int visited[101] = { 0 };
int cnt = 0;

void dfs(int now) {
	cnt++;
	for (int x = 0; x < map[now].size(); x++) {
		int next = map[now][x];
		if (visited[next] == 1) continue;
		visited[next] = 1;
		dfs(next);
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	
	cin >> N >> M;
	map.resize(N + 1);

	while (M--) {
		int start, end;
		cin >> start >> end;
		map[start].push_back(end);
		map[end].push_back(start);
	}

	visited[1] = 1;
	dfs(1);

	cout << cnt - 1; // 1번 컴퓨터 제외
}

BFS 풀이

queue 라이브러리 include 할 것

int bfs(int start) {
	queue<int> q;
	int cnt = 0;
	visited[start] = 1;

	q.push(start);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cnt++;

		for (int i = 0; i < map[now].size(); i++) {
			int next = map[now][i];
			if (visited[next] == 1) continue;
			visited[next] = 1;
			q.push(next);
		}
	}
	
	return cnt;
}

같은 그룹을 찾는 문제인것 같은데 Union-Find 알고리즘도 가능할 것 같음

---