[BOJ/Java] 2606. 바이러스

[BOJ/Java] 2606. 바이러스

2606번: 바이러스

---

문제 설명

본 문제에서는 컴퓨터 네트워크가 주어지고, 1번 컴퓨터가 바이러스에 감염되었다고 가정한다. 바이러스는 네트워크를 통해 직접 연결된 컴퓨터로만 전파될 수 있다. 주어진 네트워크에서 바이러스에 감염될 수 있는 컴퓨터의 수를 찾는 것이 목표이다. 네트워크의 연결 상태는 컴퓨터 쌍의 리스트로 제공되며, 각 쌍은 양방향 연결을 나타낸다.

풀이 과정

1. 컴퓨터 수와 연결 정보 입력받기: 네트워크에 있는 컴퓨터의 수와 각 컴퓨터 간의 연결 정보를 입력받는다.
2. 연결 정보 저장: 연결 정보를 양방향으로 저장하여 간선 리스트를 생성한다.
3. 깊이 우선 탐색(DFS) 수행: 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 방문하며 방문 횟수를 카운트한다.
4. 바이러스가 퍼진 컴퓨터 수 출력: 방문된 컴퓨터 수(1번 컴퓨터 제외)를 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No2606;

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private int n; // 컴퓨터의 총 수
    private int m; // 연결된 컴퓨터 쌍의 수
    private ArrayList<Edge> edgeList; // 연결된 컴퓨터 쌍을 저장하는 리스트
    private boolean[] visited; // 방문한 컴퓨터를 표시하는 배열
    private int ans = 0; // 바이러스에 감염된 컴퓨터의 수

    class Edge { // 컴퓨터 연결을 나타내는 내부 클래스
        int from, to;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    private void io() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        edgeList = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            edgeList.add(new Edge(from, to));
            edgeList.add(new Edge(to, from));
        }

        visited = new boolean[n];
        dfs(0);

        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int i) {
        visited[i] = true;
        for (Edge e : edgeList) {
            if (e.from == i && !visited[e.to]) {
                ans++;
                dfs(e.to);
            }
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 주로 DFS에 의해 결정된다. 최악의 경우 모든 컴퓨터를 방문해야 하며, 각 컴퓨터에 대한 연결 정보를 모두 확인해야 한다. 따라서 시간 복잡도는 O(N+M)이다, 여기서 N은 컴퓨터의 수이고 M은 연결된 컴퓨터 쌍의 수이다.