[BOJ] 2606 바이러스 - JAVA

1. 문제

https://www.acmicpc.net/problem/2606

2606번: 바이러스

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

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

---

2. 풀이

bfs로 간단하게 풀었다.

static int N;
static boolean[] visited;
static int[][] computers;

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

   N = Integer.parseInt(in.readLine());
   int M = Integer.parseInt(in.readLine());

   computers = new int[N+1][N+1];
   visited = new boolean[N+1];

   for(int i=0;i<M;i++){
      st = new StringTokenizer(in.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      computers[a][b] = computers[b][a] = 1;
   }

   System.out.println(bfs());
}

private static int bfs() {
   Queue<Integer> queue = new LinkedList<>();
   queue.offer(1);

   int cnt = 0;
   visited[1] = true;

   while(!queue.isEmpty()){
      int v = queue.poll();
      for(int i=1;i<=N;i++){
         if(computers[v][i]==1 && !visited[i]){
            queue.offer(i);
            visited[i] = true;
            ++cnt;
         }
      }
   }
   return cnt;
}

---

3. 결과