백준- 2606번 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

---

BFS를 사용하여 풀이

인접한 컴퓨터를 큐에 삽입. 또 그 인접한 컴퓨터를 큐에 삽입하여 삽입이 일어날 때마다 count 1씩 증가

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//bfs
public class 바이러스 {
	static int computerN, LinkN;//컴퓨터의 수 간선의 수
	static int arr[][];
	static boolean visit[];
	static int cnt;
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/바이러스.txt"));
		Scanner sc = new Scanner(System.in);
		computerN = sc.nextInt();//컴퓨터의수
		LinkN = sc.nextInt();//간선의수
		arr = new int[computerN+1][computerN+1];//인접행렬 인덱스1부터시작
		visit = new boolean[computerN+1];//방문배열 인덱스1부터시작
		cnt=0;
		for (int i = 0; i < LinkN; i++) {//간선의수만큼 인접행렬에 값넣기
			int a =sc.nextInt();
			int b =sc.nextInt();
			arr[a][b]=1;
			arr[b][a]=1;
		}
		//1번 컴퓨터가 웜바이러스에 걸렸을 때
		bfs(1);
		System.out.println(cnt);
	}
	private static void bfs(int v) {
		Queue <Integer> Q = new LinkedList<Integer>();
		Q.offer(v);
		visit[v]=true;
		while(!Q.isEmpty()) {
			v=Q.poll();
			for (int i = 1; i <=computerN ; i++) {
				if(arr[v][i]==1 && !visit[i]) {
					cnt++;//큐에 하나씩들어올때마다 cnt값을 플러스해줌
					Q.offer(i);
					visit[i]=true;
				}
			}
		}
	}

}