[JAVA] 백준 2606

 

 

 

2606번: 바이러스

문제

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

풀이

1번 컴퓨터와 연결된 모든 컴퓨터를 DFS 혹은 BFS로 탐색하면서 감염된 컴퓨터를 구하는 문제였다.

📌 입력

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

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

        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            A[a].add(b);
            A[b].add(a);
        }

각 컴퓨터가 1 ~ N까지 있으므로 0 ~ N까지 범위의 배열을 선언해준다.

그리고 각 노드들을 연결 리스트 형태로 양방향 연결을 해주었다.

📌 DFS

    public static void DFS(int a){
        V[a] = true;
        for(int x : A[a]){
            if(!V[x]){
                DFS(x);
                answer++;
            }
        }
    }

DFS로 모든 컴퓨터를 탐색하면서 컴퓨터의 수를 카운트해준다.

📌 출력

        DFS(1);
        System.out.println(answer);

1번 컴퓨터부터 DFS를 시작하고 결과를 출력한다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {

    static ArrayList<Integer>[] A;
    static boolean[] V;
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            A[a].add(b);
            A[b].add(a);
        }
        DFS(1);
        System.out.println(answer);

    }

    public static void DFS(int a){
        V[a] = true;
        for(int x : A[a]){
            if(!V[x]){
                DFS(x);
                answer++;
            }
        }
    }

}

결과