바이러스

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

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제

어떻게 풀까

각 노드의 값을 인덱스값으로 하여 인접한 노드의 리스트를 리스트 형태로 저장하고, bfs 구현 코드를 활용하여 인접한 노드 방문수를 센다
주의점으로는 인덱스 값이기 때문에 각 노드값에 -1
감염된 컴퓨터의 수이기 때문에 시작 노드는 카운트에 포함하지 않는다

풀이 코드

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

public class Main {

    static int N;
    static int M;

    static int comCount = -1;
    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(read.readLine());
        M = Integer.parseInt(read.readLine());

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>()); // 각 노드마다 빈 리스트를 초기화
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer stoi = new StringTokenizer(read.readLine());
            int mainNode = Integer.parseInt(stoi.nextToken())-1;
            int connectNode = Integer.parseInt(stoi.nextToken())-1;
            if (!graph.get(mainNode).contains(connectNode)) {
                graph.get(mainNode).add(connectNode);
            }
        }

        BFS(0);

        System.out.println(comCount);
    }

    private static void BFS(int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode); // 시작 노드를 큐에 추가
        visited[startNode] = true; // 시작 노드 방문 처리

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드를 꺼냄

            // 현재 노드의 인접 노드를 탐색
            for (int adjacent : graph.get(node)) {
                if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
                    queue.add(adjacent); // 큐에 추가
                    visited[adjacent] = true; // 방문 처리
                    comCount ++;
                }
            }
        }
    }
}