[백준 2606] 바이러스(Java)

문제 링크 : https://www.acmicpc.net/problem/2606

이 문제는 연결 리스트와 dfs를 이용하여 풀 수 있습니다. 연결 리스트란 노드를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 자료 구조입니다. 따라서 하나의 노드, 즉 하나의 컴퓨터와 연결되어 있는 다른 컴퓨터 값들을 컴퓨터 인덱스에 저장하여 해당 인덱스를 타고 들어가서 체크하는 방식으로 dfs를 이용하여 문제를 풀 수 있습니다.

다음은 코드입니다.

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

public class Main{
    static int N,M;
    static int res = 0;
    static ArrayList<Integer>[] req = new ArrayList[101];
    static boolean[] check = new boolean[101];

    static void dfs(int n){
        check[n] = true;
        ArrayList<Integer> curr = req[n];

        for(int i=0;i<curr.size();i++){
            int m = curr.get(i);

            if(!check[m]){
                dfs(m);
                res++;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        for(int i=0;i<101;i++){
            req[i] = new ArrayList<>();
        }

        for(int i=0;i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            req[n].add(m);
            req[m].add(n);
        }

        dfs(1);

        System.out.println(res);
    }
}