백준 2606번: 바이러스

문제 출처: https://www.acmicpc.net/problem/2606

참고

DFS(Depth-First Search): http://qlyh8.tistory.com/29?category=731166

DFS 문제: http://qlyh8.tistory.com/31?category=731166

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    private static int[][] network;
    private static boolean[] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        network = new int[N][N];
        visit = new boolean[N];
        int pair = Integer.parseInt(reader.readLine());
 
        for(int i=0 ; i<pair ; i++){
            String[] input = reader.readLine().split(" ");
            network[Integer.parseInt(input[0])-1][Integer.parseInt(input[1])-1] = 1;
            network[Integer.parseInt(input[1])-1][Integer.parseInt(input[0])-1] = 1;
        }
 
        dfs(0); // 1번 컴퓨터를 통해 웜 바이러스가 전파
 
        int count = 0;
        for (boolean aVisit : visit) {
            if (aVisit) {
                count++; // 바이러스에 걸리게 되는 컴퓨터 수 계산
            }
        }
 
        System.out.println(count-1); // 1번 컴퓨터 제외
    }
 
    private static void dfs(int computer){
      visit[computer] = true; // 바이러스 감염
 
      for(int i=0 ; i<visit.length ; i++){
          if(network[computer][i]==1 && !visit[i]){ // 감염된 컴퓨터와 연결된 컴퓨터가 감염되지 않았다면
              dfs(i); 
          }
      }
    }
}