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

코드

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

public class Main {
    private static ArrayList<ArrayList<Integer>> adjacentList;
    private static boolean[] visited;
    private static int count;

    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());

        // 컴퓨터들의 연결 정보
        adjacentList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjacentList.add(new ArrayList<>());
        }

        visited = new boolean[n + 1]; // 방문 여부 체크
        count = 0; // 1번 컴퓨터와 바이러스에 감염된 컴퓨터 개수를 저장

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adjacentList.get(a).add(b);
            adjacentList.get(b).add(a);
        }

        dfs(1);
        System.out.println(count);
    }

    private static void dfs(int start) {
        if (visited[start]) {
            return;
        }

        visited[start] = true;

        for (Integer i : adjacentList.get(start)) {
            if (!visited[i]) {
                count++;
                dfs(i);
            }
        }
    }
}

코드 설명 & 접근 방법

컴퓨터의 개수(n)는 7이고, 네트워크 상 연결 쌍(m)의 개수는 6입니다.
1부터 7까지의 인덱스로 이루어진 인접 리스트(adjacentList)를 초기화합니다.
다음은 입력된 연결 쌍에 따라 인접 리스트를 채웁니다.

adjacentList[1] = [2, 5]
adjacentList[2] = [1, 3, 5]
adjacentList[3] = [2]
adjacentList[4] = [7]
adjacentList[5] = [1, 2, 6]
adjacentList[6] = [5]
adjacentList[7] = [4]

1. dfs(1) 함수를 호출하여 1번 컴퓨터부터 깊이 우선 탐색을 시작합니다.
2. visited 배열은 각 노드의 방문 여부를 저장하는데 사용되며, count 변수는 1번 컴퓨터와 감염된 컴퓨터의 개수를 저장합니다.
3. dfs(1) 함수를 호출한 뒤, 방문하지 않은 인접 노드인 2번 컴퓨터를 찾습니다. count를 1 증가시키고, 2번 컴퓨터를 방문한 것으로 표시합니다.
   이어서 다시 dfs를 이용해 2번 컴퓨터와 연결된 미방문 노드를 찾습니다.
4. 2번 컴퓨터와 연결된 미방문 노드는 3번 컴퓨터입니다. count를 1 증가시키고, 3번 컴퓨터를 방문한 것으로 표시합니다.
   하지만, 3번 컴퓨터와 연결된 미방문 노드는 없으므로, 다시 2번 컴퓨터로 돌아가 미방문 노드를 찾습니다.
5. 그 다음 2번 컴퓨터와 연결된 미방문 노드는 5번 컴퓨터입니다. count를 1 증가시키고, 5번 컴퓨터를 방문한 것으로 표시합니다.
   이어서 다시 dfs를 이용해 5번 컴퓨터와 연결된 미방문 노드를 찾습니다.
6. 5번 컴퓨터와 연결된 미방문 노드는 6번 컴퓨터입니다.
   count를 1 증가시키고, 6번 컴퓨터를 방문한 것으로 표시합니다.
   하지만, 6번 컴퓨터와 연결된 미방문 노드는 없으므로 여기서 dfs 탐색이 끝납니다.
7. 모든 탐색이 종료되면, 1번 컴퓨터와 연결된 컴퓨터의 개수가 저장된 count 값을 출력합니다.
   앞서 말했던 예제 들에서는 count 값이 4로 계산되므로, 결과로 4를 출력합니다.