[2606] 바이러스 (JAVA)

# 문제 설명

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

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    static boolean[] visited; //방문 체크 배열(1~N)
    static ArrayList<Integer>[] A; //인접 리스트(1~N)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N =  Integer.parseInt(st.nextToken()); //컴퓨터의 수
        st = new StringTokenizer(br.readLine());
        int E =  Integer.parseInt(st.nextToken()); //연결된 컴퓨터 쌍의 수

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

        for (int e = 0; e < E; e++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            A[n1].add(n2);
            A[n2].add(n1);
        }

        dfs(1);

        int cnt = 0;
        for (boolean v : visited) {
            if (v) {
                cnt++;
            }
        }

        System.out.print(cnt-1);
    }

    public static void dfs(int v) {
        if (visited[v]) {
            return;
        }

        visited[v] = true;
        for (int i : A[v]) {
            dfs(i);
        }
    }
}

 

dfs를 이용하여 바이러스에 걸린 컴퓨터 수를 구했다.

입력받은 연결된 컴퓨터 쌍의 수를 인접 리스트에 추가한다.

 

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 구해야하므로 1번 노드를 시작으로 dfs를 실행한다.

현재 노드 v가 방문한 노드이면 종료한다.

그렇지 않으면, 방문 체크 배열에서 v를 true로 바꾸고 v와 인접한 노드를 탐색한다.

 

dfs 실행이 끝난 후, 방문 체크 배열에서 true인 노드의 개수를 cnt에 저장한다.

구한 cnt에서 1번 컴퓨터의 수를 뺀 값인 cnt-1을 출력한다.

 

# 다른 풀이 1

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

public class Main {
    static boolean[] visited; //방문 체크 배열(1~N)
    static ArrayList<Integer>[] A; //인접 리스트(1~N)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //컴퓨터의 수
        st = new StringTokenizer(br.readLine());
        int E = Integer.parseInt(st.nextToken()); //연결된 컴퓨터 쌍의 수

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

        for (int e = 0; e < E; e++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            A[n1].add(n2);
            A[n2].add(n1);
        }

        bfs(1);

        int cnt = 0;
        for (boolean v : visited) {
            if (v) {
                cnt++;
            }
        }

        System.out.print(cnt-1);
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int n : A[now]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

 

bfs를 이용하여 풀었다.

1번 노드를 시작으로 bfs를 실행한다.

 

큐를 만들고 현재 노드 v를 넣는다. 방문 배열을 true로 바꿔준다.

큐가 빌 때까지 큐에 있는 노드를 꺼내어 now에 저장한다.

now의 인접 노드를 방문하지 않았으면 방문 배열을 true로 바꾸고 큐에 넣는다.

 

bfs가 끝나고 visited에서 true인 노드의 개수를 cnt에 저장한다.

cnt에서 1번 컴퓨터를 뺀 값인 cnt-1을 출력한다.