[백준] 바이러스 - Silver 3

[jusung-c]

문제 링크

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

문제 조건

• 바이러스는 네트워크에 연결된 모든 컴퓨터를 전염시킨다.
• 1번 컴퓨터가 바이러스가 걸렸다면 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구하라
• 컴퓨터의 수는 100 이하이다.

---

아이디어

• 1번 컴퓨터부터 시작해서 DFS를 진행한다.
• DFS를 진행할 때마다 카운트를 해준다.

---

시간 복잡도

DFS의 시간 복잡도는 O(V+E)이다. V의 최댓값은 100이고, E의 최댓값은 모든 차수의 합을 더해 2를 나누면 된다. 따라서 100*99/2로 시간 안에 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
    static StringTokenizer st;
    static int N, K, cnt;
    static ArrayList<Integer>[] adj;
    static boolean[] visit;

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        visit = new boolean[N + 1];
        cnt = 0;

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

        for (int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            adj[x].add(y);
            adj[y].add(x);
        }

        dfs(1);

        bw.write(cnt - 1 + " ");
    }

    private static void dfs(int x) {
        visit[x] = true;
        cnt++;

        for (int y : adj[x]) {
            if (visit[y]) continue;
            dfs(y);
        }
    }

    private static void pro() throws IOException {


    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}