[백준 2606번] 바이러스

문제 링크: 2606번 바이러스

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

 

서로 연결된 노드들의 집합 개수를 구하는 문제이다. 1번 컴퓨터와 네트워크 상에서 직접 연결된 컴퓨터의 수를 구하면 되므로, 모든 탐색을 끝마친 후 visit 배열의 true 개수를 모두 세고, 1번 컴퓨터를 뺀 값을 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
​​​​public static void main(String[] args) throws IOException {
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

​​​​​​​​int computers = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
​​​​​​​​int pairs = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

​​​​​​​​ArrayList<Integer>[] graph = new ArrayList[computers];
​​​​​​​​boolean[] visited = new boolean[computers];

​​​​​​​​for (int i = 0; i < computers; i++)
​​​​​​​​​​​​graph[i] = new ArrayList<Integer>();

​​​​​​​​for (int i = 0; i < pairs; i++) {
​​​​​​​​​​​​int[] temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
​​​​​​​​​​​​int start = temp[0] - 1;
​​​​​​​​​​​​int end = temp[1] - 1;
​​​​​​​​​​​​graph[start].add(end);
​​​​​​​​​​​​graph[end].add(start);
​​​​​​​​}

​​​​​​​​Queue<Integer> queue = new LinkedList<>();
​​​​​​​​queue.offer(0);
​​​​​​​​visited[0] = true;

​​​​​​​​while (!queue.isEmpty()) {
​​​​​​​​​​​​int cur = queue.poll();
​​​​​​​​​​​​for (int connected : graph[cur]) {
​​​​​​​​​​​​​​​​if (!visited[connected]) {
​​​​​​​​​​​​​​​​​​​​visited[connected] = true;
​​​​​​​​​​​​​​​​​​​​queue.offer(connected);
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​int cnt = 0;
​​​​​​​​for (boolean item : visited)
​​​​​​​​​​​​if (item)
​​​​​​​​​​​​​​​​cnt++;

​​​​​​​​System.out.println(cnt-1);
​​​​}
}