[JAVA] 백준 2606_바이러스

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

📌 문제 탐색하기

 

컴퓨터 번호 1번 부터 시작 -> 1번 컴퓨터부터 시작해서 몇대의 컴퓨터가 감염되는지 찾아서 출력하는 문제이다. 

 

📌 가능한 시간복잡도

입력받은 컴퓨터의 수  N대, 네트워크 상에 직접 연결되어 잇는 컴퓨터 쌍의 수 M이므로  BFS를 활용해서 
가능한 시간복잡도는 O(N+M)입니다. 

📌 코드 설계하기

BFS 활용
정점 : 컴퓨터(컴퓨터 번호는 1부터 시작) / 간선 : 네트워크 연결으로 설정해서 
감염된 컴퓨터 수는 1번 컴퓨터를 제외하고 COUNT한다. 

📌 정답 코드

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

public class Main {
    public static int bfs(List<List<Integer>> graph, boolean[] visited, int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        int infected = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                    infected++;
                }
            }
        }

        return infected;
    }

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

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= computer; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < pair; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        boolean[] visited = new boolean[computer + 1];
        int result = bfs(graph, visited, 1);
        System.out.println(result);
    }
}