[백준 2606] 바이러스 (JAVA)

백준 2606번 문제 - 바이러스

2606번: 바이러스

---

문제 분석

 

 

• 컴퓨터들은 연결되어 있으면 연결되어있는 한 컴퓨터만 감염될 시 다 감염된다.
• 1번 컴퓨터가 감염됬을 때 몇개가 감염되는지 출력해라.

---

해결 키 포인트

 

• BFS 문제
• 1번과 연결된 컴퓨터의 수 = 같이 감염되는 수
• 단순하게 1번과 연결된 컴퓨터를 BFS로 한번 알아보면 된다.

---

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int computerN = Integer.parseInt(br.readLine());
        int pairN =  Integer.parseInt(br.readLine());

        ArrayList<Integer> [] pairs = new ArrayList[computerN+1];
        for (int i = 1; i <= computerN; i++) {
            pairs[i] = new ArrayList<>();
        }

        for (int i = 0; i < pairN; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            pairs[a].add(b);
            pairs[b].add(a);
        }

        System.out.println(BFS(pairs, 1));
    }

    static public int BFS(ArrayList<Integer> [] pairs, int index) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean [] visited = new boolean[pairs.length];

        queue.add(index);
        visited[index] = true;

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

            ArrayList<Integer> pair = pairs[newIndex];
            for(int i=0;i<pair.size();i++) {
                int num = pair.get(i);
                if(!visited[num]) {
                    queue.add(num);
                    visited[num] = true;
                    count++;
                }
            }
        }

        return count;
    }

}