📝 문제 설명

  • 웜 바이러스는 네트워크를 통해 퍼진다.
  • 한 컴퓨터가 감염되면, 직접 연결된 모든 컴퓨터도 감염된다.
  • 1번 컴퓨터가 감염되었을 때, 총 몇 대의 컴퓨터가 감염되는가? (1번 제외)
  1. 입력
    • 첫째 줄에는 컴퓨터의 수 N을 입력 받는다.
    • 둘째 줄에는 네트워크 상에서 서로 연결되어있는 컴퓨터의 개수 M을 입력 받는다.
    • 이어서 그 수(M)만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어있는 번호 쌍을 입력받는다.
  2. 출력
    • 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

웜바이러스 그래프

문제 링크

💡 아이디어

  • 컴퓨터는 정점(vertex), 직접 연결된 컴퓨터 쌍은 간선(edge) 으로 간주하여 그래프 탐색(Graph Traversal) 문제로 해석한다.
  • 간결한 구현을 위해 깊이 우선 탐색(DFS)을 사용한다.
  • 정석적인 DFS 구현에서 전역변수 count를 추가하여, 바이러스에 감염된 컴퓨터의 수를 계산한다.

DFS 구현에서는 1번 컴퓨터에서 탐색을 시작함을 명시한다.
애초에 DFS는 시작 정점과 연결된 정점들만 순차적으로 탐색하기 때문에,
1번과 연결되지 않은 컴퓨터는 자연스럽게 탐색 대상에서 제외된다.
즉, 1번 컴퓨터를 통해 실제로 감염되는 컴퓨터만 정확히 집계되는 구조가 된다.

🛠 코드

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

public class Main {
    static int count = 0;
    static List<Integer>[] adj;
    static boolean[] infected;

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

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

            adj[a].add(b);
            adj[b].add(a);
        }

        infected = new boolean[N + 1]; // 1번 컴퓨터에 의해 감염된 컴퓨터 개수 계산
        count = 0; // 전역변수기때문에 반드시 초기화가 필요함
        worm(1); // 1번 컴퓨터 감염시작(이 문제는 확정임)
        System.out.println(count); // 감염된 컴퓨터 수 (1번 제외)
    }

    static void worm(int w) {
        infected[w] = true;
        for (int nxt : adj[w]) {
            if (!infected[nxt]) {
                count++;  // 새로 감염된 컴퓨터만 카운트 (시작하는 1은 자연스럽게 빠짐)
                worm(nxt);
            }
        }
    }
}

⏱ 시간 복잡도

  • 입력 처리:
    M개의 간선 정보를 읽고 양방향 인접 리스트에 저장 → O(M)

  • 그래프 탐색:
    1번 컴퓨터에서 시작해 감염된 정점만 탐색 → 평균적으로는 O(K) (K는 연결된 컴퓨터 수)
    최악의 경우, 모든 정점과 간선을 한번씩 탐색 → O(N + M)

  • 출력:
    감염된 컴퓨터 수 1개 출력 → O(1)

👉 총 시간 복잡도 (최악의 경우):
O(N + M)

✏️ 느낀 점

  • 필터링 로직 없이도 탐색으로 필터링 되는 구조구나