[BOJ] 2606: 바이러스(JAVA)

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

2606번: 바이러스

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

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

입력

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

출력

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

예제 입력 1 

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력 1 

4

 

---

[문제 풀이]

각 컴퓨터의 연결 정보를 2차원 boolean 배열 linked에 저장하였다.

만약 1, 2번 컴퓨터가 연결되어 있다면, linked[1][2]와 linked[2][1]은 true이다.

 

count는 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 의미한다. 바이러스에 걸리게 된 컴퓨터 수 중 1번 컴퓨터가 바이러스가 걸린 경우는 포함하지 않는다.

 

연결 정보를 이용해 DFS로 count를 계산할 것이다.

boolean배열 visit은 해당 컴퓨터를 count 또는 방문했는지 여부이다. 

dfs 함수에서

1. 해당 컴퓨터를 방문했다면 return;

2. 방문하지 않았다면 visit[컴퓨터] = true로 변경하고 해당 컴퓨터 번호가 1번이 아니라면 count를 1 증가시킨다.

3. 반복문으로 i를 1부터 N까지 증가시키며 i번 컴퓨터를 방문하지 않았고, i번째 컴퓨터와 현재 컴퓨터가 연결되어있다면 dfs(i)를 다시 호출한다.

 

dfs함수가 모두 종료되고 나면 count를 출력하고 종료한다.

   

[코드]

import java.util.*;

public class Main{
   static int count=0, N;
   static boolean[][] linked;
   static boolean[] visit;
   public static void dfs(int v) {
     if(visit[v])
       return;

     visit[v]=true;
     if(v!=1)
       count++;
     for(int i=1;i<=N;i++) {
       if(!visit[i]&&linked[v][i])
       dfs(i);
     }
   }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int M = sc.nextInt();
        linked =new boolean[N+1][N+1];
        visit = new boolean[N+1];
        for(int i=0;i<M;i++) {
          int a=sc.nextInt();
          int b=sc.nextInt();
    
          linked[a][b]=true;
          linked[b][a]=true;
       }
    
        dfs(1);
        System.out.println(count);
  
    }
}