[백준][DFS] 바이러스

https://www.acmicpc.net/problem/2606

 

package bkjoon.dfs;

import java.util.*;

class Node {
    int id; // 컴퓨터 번호
    List<Node>  children; // 연결된 컴퓨터들

    Node(int id) {
        this.id = id;
        this.children = new ArrayList<>();
    }
}
public class bk2606 {

    /**
     * DFS - 바이러스
     * 실버3
     */

    static boolean[] visited; // 방문여부 체크
    static int infectedCount = 0; // 감염된 컴퓨터 숫자

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 컴퓨터의 수
        int m = sc.nextInt(); // 네트워크 연결 수

        // Node배열(1번부터 사용)
        Node[] computers = new Node[n+1];
        for(int i = 1; i <= n; i++){
            computers[i] = new Node(i);
        }

        // 네트워크 연결(양방향연결)
        for(int i = 0; i < m; i++){
            int u = sc.nextInt(); // 컴퓨터1
            int v = sc.nextInt(); // 컴퓨터2
            // 양방향 연결시키기
            computers[u].children.add(computers[v]);
            computers[v].children.add(computers[u]);
        }

        visited = new boolean[n+1]; // 방문 여부를 담는 배열 visited

        dfs(computers[1]);  // 1번 컴퓨터가 바이러스에 걸릴 경우를 시작

        System.out.println(infectedCount-1);
    }

    // 넓이 우선 탐색
    static void dfs(Node node){
        visited[node.id] = true; // 방문함으로 변경
        infectedCount++; // 감염된숫자를 추가

        for(Node child: node.children){
            // 방문하지 않았다면
            if(!visited[child.id]){
                dfs(child);
            }
        }
    }

}