2606번 : 바이러스

2606번 : 바이러스

* 문제 출처 : 백준 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_2606 {
    static int[][]map;
    static boolean[] visit;
    static int com;
    static int cnt;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        com = Integer.parseInt(br.readLine()); //컴퓨터 수
        int con = Integer.parseInt(br.readLine()); //연결되어 있는 컴퓨터 쌍의 수
        map = new int[com+1][com+1]; //좌표
        visit = new boolean[com+1]; //방문 여부
 
        StringTokenizer st;
        for (int i = 0; i < con; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = map[y][x] =1; //서로 연결
        }
        cnt = 0; //바이러스 횟수
 
        dfs(1); //1번부터 시작
 
        System.out.println(cnt);
    }
 
    static void dfs(int depth) { //현재 컴퓨터 번호
        if (visit[depth]) { //현재 컴퓨터 번호를 방문 했으면 돌아감
            return;
        }
        
        if (depth >com) { //컴퓨터 번호가 컴퓨터의 수를 증가하면 돌아감
            return;
        }
        
        //현재 컴퓨터 번호를 방문하지 않았다면 
        visit[depth] = true; //방문 체크
        
        for (int i = 1; i <= com; i++) {
            if (!visit[i] && map[i][depth]==1) { //방문하지 않았고 현재 컴퓨터 번호와 연결되어 있는 경우
                cnt++; //감염 횟수를 1증가
                dfs(i); //i번째 컴퓨터 dfs
            }
        }
    }
 
}