[BOJ] 바이러스(2606)

www.acmicpc.net/problem/2606

2606번: 바이러스

난이도 - 실버1

분류 - DFS, BFS

문제

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

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

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

입력

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

출력

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

 

코드

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

public class Main{
    static int N, M;
    static ArrayList<Integer>[] mtx;		// N*N 배열을 사용하는 것보다 적은 탐색 시간이 걸린다.
    static boolean[] check;
    static int[] dy = {1,-1, 0, 0};
    static int[] dx = {0, 0, 1,-1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        mtx = new ArrayList[N+1];
        check = new boolean[N+1];
        for (int i = 0; i <= N; i++) {
            mtx[i] = new ArrayList<>();
        }
        int a,b;
        while(M-->0){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            mtx[a].add(b);
            mtx[b].add(a);
        }
	////////////////// 입력 ////////////////////
        int ans =-1;		// 1번 노드는 count하지 않기 때문에 -1에서 시작하여
        					// 1번노드를 탐색할때 ans가 0이 되도록 한다.
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        check[1]=true;
        while(!q.isEmpty()){
            int now = q.poll();
            ans++;
            for(int i =0; i< mtx[now].size(); i++){
                int next =mtx[now].get(i);
                if(check[next]) continue;
                check[next]=true;
                q.add(next);
            }

        }
        System.out.println(ans);

    }

}

풀이

사실 이런 간단한 문제는 DFS가 더 쉽게 구현 할 수 있지만 오늘은 BFS로 구현해봤습니다.

단순하게 DFS나 BFS를 통해 모든 노드를 탐색하면 되는 문제입니다.

 

다른사람의 코드를 보니 이것을 분리집합을 이용하여 풀이하신 분도 있던데 덕분에 다양한 방법에 대해 생각해볼 수 있었네요