[Java] BOJ 2606 바이러스

문제 

문제 링크 https://www.acmicpc.net/problem/2606

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

  

• 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
• 첫째 줄에는 컴퓨터의 수가 주어진다.
• 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
• 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
• 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

아이디어

• HashSet 배열을 만들어서 그 배열에 컴퓨터 연결정보를 저장한다. (HashSet을 사용하는 이유는 컴퓨터 번호를 중복 저장하지 않기 위해서이다.)
• 그리고 N+1 크기의 boolean 배열을 만들어서 방문여부를 체크한다. 
• 우선 컴퓨터가 서로 연결되어 있는 정보를 입력받을 때, [a]배열에 b를 저장하고 [b]배열에 a를 저장한다.
• 그리고 BFS를 돌린다. 
• Queue에 처음에 찾을 컴퓨터 번호를 넣고 해당 번호를 방문 처리를 한다.
• 그리고 while문을 Queue가 비어질때까지 돌면서 Queue에서 맨 위의 값을 빼고 해당 값을 결과를 저장하는 ArrayList에 저장한다.
• 그리고 해당 번호에 연결되어있는 컴퓨터 번호들 중 방문하지 않은 번호가 있다면, 해당 번호를 방문처리하고 Queue에 그 번호를 넣는다.
• 계속 반복하다보면 처음에 찾을 컴퓨터 번호와 연결된 번호들이 Queue에 들어갔다가 나오면서 결과값을 저장하는 ArrayList에 저장된다.
• 그리고 결과를 출력할때, 결과값을 저장하는 ArrayList에서 1을 빼고 출력한다. (해당 ArrayList에 초기 컴퓨터 번호도 저장이 되어있으므로, 본인 번호는 빼야되기 때문)

겪은 시행착오

• 오랜만에 BFS를 써서 조금 시간이 걸렸던 것 같다.... (앞으로 나올 그래프 문제들... 긴장된다... ㅜㅜ)

파이팅!!! 그래프 문제들...!! 기다려라!!!

코드

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

public class BOJ2606 {
    static Set<Integer> worm[];
    static Set<Integer> result;
    static boolean visited[];

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

        // 컴퓨터 개수
        int N = Integer.parseInt(br.readLine());

        // 컴퓨터 쌍의 수
        int C = Integer.parseInt(br.readLine());

        // 컴퓨터 연결 저장할 HashSet 배열
        worm = new HashSet[N + 1];

        // HashSet으로 초기화
        for (int i = 0; i <= N; i++) {
            worm[i] = new HashSet<>();
        }
        // 결과 컴퓨터를 저장할 set (중복 값이 들어가면 안되므로)
        result = new HashSet<>();

        // 방문 여부
        visited = new boolean[N + 1];

        for(int i = 0; i < C; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            // 컴퓨터 번호 입력
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 해당 컴퓨터에 양방향으로 연결
            worm[a].add(b);
            worm[b].add(a);

        }

        BFS(1);

        // 해당 결과 ArrayList에 본인 번호도 포함되어 있으므로 1을 뺌
        System.out.println(result.size() - 1);
    }

    public static void BFS(int c){
        Queue<Integer> q = new LinkedList<>();

        // queue에 찾을 컴퓨터 번호를 넣어줌
        q.offer(c);
        // 해당 번호 방문 처리
        visited[c] = true;

        // queue가 빌때까지 반복
        while(!q.isEmpty()){
            // queue에 들어있는 번호를 꺼냄
            int num = q.poll();

            // 결과값을 저장할 배열에 해당 번호 저장
            result.add(num);

            // 해당 번호 컴퓨터에 연결된 컴퓨터 번호들 중
            for(int i : worm[num]){
                // 방문하지 않은 곳이 있다면
                if(!visited[i]){
                    // 방문 처리 후
                    visited[i] = true;

                    // queue에 해당 번호를 넣음
                    q.offer(i);
                }
            }
        }
    }
}