바이러스(백준 2606) - DFS

정답 및 해설

package A0study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class p2606_바이러스 {
    static ArrayList<Integer>[] graph; // 인접 리스트
    static boolean[] visited;          // 방문 체크
    static int count = 0;              // 감염된 컴퓨터 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());    // 컴퓨터 수(=노드)
        int M = Integer.parseInt(br.readLine());    // 연결 쌍 수(=엣지)

        // 그래프 초기화
        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 연결 정보 입력
        for(int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u].add(v);
            graph[v].add(u);    // 양방향
        }

        visited = new boolean[N+1];

        dfs(1); // 1번 컴퓨터부터 시작

        System.out.println(count);
    }

    static void dfs(int node) {
        visited[node] = true;
        for(int next : graph[node]) {
            if(!visited[next]) {
                count++;    // 감염된 컴퓨터 수 증가
                dfs(next);  // 재귀 호출
            }
        }
    }
}