백준 No.2606 바이러스 - JAVA

 

 

 

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림1> 과 같이 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번의 컴퓨터는 1번 컴퓨터와 네트워크 상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 

ㅇ어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오

 

 

풀이

 

전형적인 탐색인데 DFS로도 풀 수 있다는 생각이 들지만 BFS로 풀었다. 애초에 탐색은 간선이 연결되어 있어야만 가능하기에 간선이 연결되어 있지 않은 곳은 탐색시도를 할 수 없다. 그렇기에 문제도 기본 탐색 코드에서 카운트만 추가하면 풀 수 있는 문제이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static boolean visited[];
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int N,M;
    static int count = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M  = Integer.parseInt(br.readLine());
        StringTokenizer st;
        visited = new boolean[N+1];

        for(int i=0;i<=N;i++){
            graph.add(new ArrayList<>());
        }

        for(int i = 0;i < M;i++){
            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);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;

        while (!queue.isEmpty()){

            int now = queue.poll();
            for(int i=0;i<graph.get(now).size();i++){
                int next = graph.get(now).get(i);
                if(!visited[next]){
                    visited[next] = true;
                    queue.add(next);
                    count++;
                }
            }
        }
        System.out.println(count);

    }



}