[BOJ 2606] 바이러스

 

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

// Press Shift twice to open the Search Everywhere dialog and type `show whitespaces`,
// then press Enter. You can now see whitespace characters in your code.
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int n = Integer.parseInt(tk.nextToken());
        List<Integer>[] list = new ArrayList[n+1];
        for(int i = 1; i < n+1; i++){
            list[i] = new ArrayList<>();
        }

        tk = new StringTokenizer(in.readLine(), " ");
        int v = Integer.parseInt(tk.nextToken());

        for(int i = 0; i < v; i++){
            tk = new StringTokenizer(in.readLine(), " ");
            int idx = Integer.parseInt(tk.nextToken());
            int go = Integer.parseInt(tk.nextToken());
            list[idx].add(go);
            list[go].add(idx);
        }

        int ans = BFS(list,n);
        System.out.println(ans);
    }

    private static int BFS(List<Integer>[] list,int size) {

        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        int ans = 0;
        boolean[] visited = new boolean[size+1];
        visited[1] = true;
        while(!q.isEmpty()){
            int n = q.poll();
            for (int i = 0; i < list[n].size(); i++) {
                if(!visited[list[n].get(i)]) {
                    visited[list[n].get(i)] = true;
                    ans++;
                    q.add(list[n].get(i));
                }
            }
        }
        return ans;
    }
}

설명이 크게 필요 없는 듯하다. BFS를 사용하였고 적절히 방문여부를 체크하였다.

 

 

2606번: 바이러스