[알고리즘] 백준 2606 : 바이러스 - JAVA

문제

2606번: 바이러스

문제이해

한 컴퓨터가 웜바이러스에 걸리리면 그 컴퓨터와 연결되어있는 네트워크 상의 모든 컴퓨터가 감염되게 된다. 컴퓨터와 네트워크는 그래프의 형식으로 주어질 때 웜바이스에 걸리게 되는 컴퓨터의 수 구하는 문제이다.

 

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

• N : 컴퓨터 수
• M : 컴퓨터의 연결 수
• A B : 각 연결된 컴퓨터의 번호

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

---

풀이

 

DFS를 이용하여 그래프를 순회하고 카운트하였습니다.

---

코드

import java.util.Scanner;

public class Main {
    static ArrayList<ArrayList<Integer>> network;
    static boolean[] visited;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //  입력 및 초기화
        int N = sc.nextInt();
        int M = sc.nextInt();

        network = new ArrayList<>();

        for(int i = 0; i < N; i++){
            network.add(new ArrayList<>());
        }
        for(int i = 0; i < M; i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            network.get(a).add(b);
            network.get(b).add(a);
        }
        
        visited = new boolean[N];
        answer = -1;
        dfs(0);

        System.out.println(answer);
    }

    public static void dfs(int current){
        visited[current] = true;
        answer++;
        //  연결된 컴퓨터에서 방문하지 않은 컴퓨터로 이동
        for(int i : network.get(current)){
            if(!visited[i]){
                dfs(i);
            }
        }
    }
}