[BOJ] 2606. 바이러스

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

2606번: 바이러스

풀이

1. 1번 컴퓨터에 연결된 컴퓨터들을 구하면 되는 연결 요소 문제이다. BFS로 풀어주면 될 것 같다.
2. 먼저 컴퓨터들의 연결 정보를 인접리스트로 구현해준다.
3. 1번 컴퓨터를 먼저 큐에 넣고 1번 컴퓨터와 연결된 컴퓨터들을 모두 방문 체크한다.
4. 방문한 컴퓨터(감염된 컴퓨터) 수를 출력 (1번 컴퓨터 제외).

 

 

import java.util.*;

public class Main {
	
	static ArrayList&ltInteger>[] list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int connect = sc.nextInt();
		list = (ArrayList[]) new ArrayList[n];
		for(int i=0; i < n; i++) {
			list[i] =  new ArrayList();
		}	
		for(int i=0; i < connect; i++) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			list[u].add(v);
			list[v].add(u);
		}
		boolean[] check = new boolean[n];
		Queue q = new LinkedList();
		q.add(0);
		check[0] = true;
		while(!q.isEmpty()) {
			int u = q.remove();
			for(int i=0; i < list[u].size(); i++) {
				int v = list[u].get(i);
				if(check[v]) continue;
				q.add(v);
				check[v] = true;
			}
		}
		int ans = -1;
		for(int i=0; i < n; i++) {
			if(check[i]) ans++;
		}		
		System.out.println(ans);
	}

}