[백준2606] 바이러스 [java]

---

이 문제는 dfs나 bfs나 상관없다고 생각하지만 bfs를 사용하면 큐를 이용해야 할 것 같아서 dfs를 사용했다.

 

트리를 표현하기 위해서 연결리스트방법을 사용했다

리스트안에 리스트를 넣어서 연결된 노드들을 표현했다. 또한 1부터 시작하므로 리스트에 크기를 1~주어진 크기보다+1을 해줬다.

 

코드

package baekjoon;

import java.util.ArrayList;
import java.util.Scanner;

public class virus {
    public static ArrayList<Integer> list[];
    public static boolean check[];
    static int cnt = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int com = scan.nextInt();
        int line = scan.nextInt();

        list = new ArrayList[com+1];
        check = new boolean[com+1];

        for(int i = 1; i<com+1; i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 1; i<line+1;i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            list[a].add(b);
            list[b].add(a);
        }
        dfs(1);
        System.out.println(cnt-1);
    }
    public static void dfs(int cur){
        if(check[cur]){
            return;
        }
        check[cur] = true;
        cnt++;
        for(int i : list[cur]){
            if(!check[i]){
                dfs(i);
            }
        }
    }
}