자바(백준) 2606 바이러스

import java.io.*;
import java.util.*;
 
public class Main {
    static boolean[] visit;
    static ArrayList<Integer> [] ad;
    static int nV, nE;
    static Queue<Integer> Q;
    public static void main(String []args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            nV = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
 
            nE = Integer.parseInt(st.nextToken());
 
            visit = new boolean[nV+1];
            ad = new ArrayList[nV+1];
 
            for(int i = 1; i <= nV; i++)
                ad[i] = new ArrayList<>();
 
            for(int i = 0; i < nE; i++){
                st = new StringTokenizer(br.readLine());
                int t1 = Integer.parseInt(st.nextToken());
                int t2 = Integer.parseInt(st.nextToken());
 
                ad[t1].add(t2);
                ad[t2].add(t1);
            }
            System.out.print(bfs(1));
 
        }
 
        public static int bfs(int start){
            int cnt = 0;
            Q = new LinkedList<>();
            Q.add(start);
            visit[start] = true;
            while(!Q.isEmpty()){
                int element = Q.poll();
                for(int index : ad[element]){
                    if(!visit[index]){
                        Q.add(index);
                        visit[index] = true;
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    }
 
 

바이러스 문제는 저번에 DFS를 공부하면서 풀어보았던 문제이다. 하지만 DFS로 풀지 않고 이번에는 BFS로 풀어보았다. 

 

궁금한 점은 BFS가 DFS보다 빠르다고 생각했는데 막상 시간을 보니, 비슷한거 같아 아직 N의 크기가 많이 크지 않아 차이가 별로 안나는 것인가 했다. 아래가 DFS로 푼 것이고, 위에 부분이 BFS로 푼 것이다.