[백준] | JAVA, 자바 | 2606번 - 바이러스

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

---

문제 요약 :

1. 컴퓨터의 수 입력받기

2. 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 입력받기

3. 입력받은 컴퓨터 쌍의 수 만큼 연결 정보 입력받기

4.  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));
        
        // 1. 컴퓨터의 수 입력받기
        int computer = Integer.parseInt(br.readLine());
        //2. 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수 입력받기
        int connection = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] list = new ArrayList[computer + 1];
        for (int i = 0; i < computer + 1; i++) {
            list[i] = new ArrayList<>();
        }

        //3. 입력받은 컴퓨터 쌍의 수 만큼 연결 정보 입력받기
        for (int i = 0; i < connection; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 양방향이기 때문에 둘 다 추가
            list[x].add(y);
            list[y].add(x);
        }
        //4.  1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성
        System.out.println(bfs(list, computer));
    }

    private static int bfs (ArrayList<Integer>[] list, int computer) {
        boolean[] visited = new boolean[computer + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        visited[1] = true;

        int cnt = 0;

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            for (int next : list[temp]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}