[알고리즘 문제 풀이] 백준 2606번 바이러스 (BFS/DFS)

 

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



public class Main{

    static int n,m;
    //static int[][] arr;
    static ArrayList<ArrayList<Integer>> arr;
    static boolean[] visited;
    static Queue<Integer> q;
    static int count;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // node 개수
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        // 간선의 수
        m = Integer.parseInt(st.nextToken());


        arr =new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n+1;i++){
            arr.add(new ArrayList<Integer>());
        }

        visited=new boolean[n+1];

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

            int node1 = Integer.parseInt(st.nextToken()) ;
            int node2 = Integer.parseInt(st.nextToken()) ;

            // 간선 표현. 1이라면 연결되어 있다는 의미임.
            arr.get(node1).add(node2);
            arr.get(node2).add(node1);
        }

        bfs(1);
        
        System.out.println(count);


    }

    static void bfs(int start){
        q= new LinkedList<>();
        q.offer(start);
        visited[start]=true;

        while(!q.isEmpty()){
            int x= q.poll();
            for(int i=0;i<arr.get(x).size();i++){
                int y = arr.get(x).get(i);
                if(!visited[y]){
                    q.offer(y);
                    visited[y]=true;
                    count++;
                }
            }


        }
    }
}