백준 2606번, 바이러스 (with. Java)

백준 2606번, 바이러스 (with.Java) 에 대하여 알아본 글입니다.

코딩 테스트 문제를 풀며, 풀었던 문제에 대한 회고와 다른 풀이 방법을 알아보며, 알아가고자 합니다.

문제에 대해 먼저 알아보겠습니다.

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.

한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.

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

입력

첫째 줄에는 컴퓨터의 수가 주어진다.

컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.

둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.

이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

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

문제 풀이

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        List<Integer>[] network = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            network[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            network[a].add(b);
            network[b].add(a);
        }

        boolean[] visited = new boolean[N + 1];
        int infectedCount = dfs(1, network, visited) - 1;

        System.out.println(infectedCount);
    }

    private  static int dfs(int node, List<Integer>[] network, boolean[] visited){
        visited[node] = true;
        int count = 1;

        for(int next : network[node]){
            if(!visited[next]){
                count += dfs(next, network, visited);
            }
        }

        return count;
    }
}

풀이 설명

이 코드는 웜 바이러스가 1번 컴퓨터에서 시작될 때 감염되는 컴퓨터의 수를 계산하는 프로그램입니다.

먼저 BufferedReader를 사용하여 입력을 받습니다.

첫 번째 줄에서 컴퓨터의 개수 N을 입력받고, 두 번째 줄에서 네트워크 상에서 직접 연결된 컴퓨터 쌍의 개수 M을 입력받습니다.

이후 M개의 줄을 읽으며 두 개의 정수를 입력받아 서로 연결된 컴퓨터를 나타냅니다.

이를 저장하기 위해 List<Integer>[] network = new ArrayList[N + 1];을 선언하여 1부터 N까지 각 컴퓨터의 연결 정보를 저장할 리스트 배열을 생성합니다.

이후 for 문을 이용해 network[i] = new ArrayList<>();를 수행하여 각 배열 요소를 실제 ArrayList로 초기화합니다.

네트워크 정보를 입력받을 때 network[a].add(b);와 network[b].add(a);를 사용하여 양방향 연결을 저장합니다.

감염된 컴퓨터를 추적하기 위해 boolean[] visited = new boolean[N + 1];을 선언하여 방문 여부를 기록합니다.

감염된 컴퓨터 수를 계산하기 위해 깊이 우선 탐색(DFS)을 수행하는 dfs 메서드를 만듭니다.

이 함수는 현재 방문한 컴퓨터를 visited 배열에 기록하고, 연결된 컴퓨터를 순차적으로 탐색하며 방문하지 않은 컴퓨터가 있다면 재귀적으로 dfs를 호출하여 감염된 컴퓨터의 개수를 누적합니다.

초기 감염된 컴퓨터가 1번이므로 dfs(1, network, visited) - 1;을 수행하여 1번 컴퓨터를 제외한 감염된 컴퓨터의 수를 계산하고 이를 출력합니다.