[BOJ] 백준 2606 바이러스

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

 Input 

7

6

1 2

2 3

1 5

5 2

5 6

4 7

 

　 

 Output 

4

　

『1』 컴퓨터를 시작 정점으로 연결되어 있는 모든 정점의 개수를 찾습니다.

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
        int connect = Integer.parseInt(sc.next());
         
        int[][] com = new int[N+1][N+1];
         
         
        for(int i=0; i<connect; i++) {
            int x = Integer.parseInt(sc.next());
            int y = Integer.parseInt(sc.next());
             
            com[x][y] = 1; com[y][x] = 1;
        }
         
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
         
        queue.add(1);
        visited[1] = true;
         
        // 1번 컴퓨터 자체는 counting에서 제외
        int count = 0;
        while(!queue.isEmpty()) {
            int curComputer = queue.poll();
             
            // 현재 컴퓨터와 연결유무를 확인
            for(int i=1; i<=N; i++) {
                // 자기자신이 아니면서 현재 노드와 연결되었으며 아직 감염(방문)되지 않은 컴퓨터라면...
                if(com[curComputer][i] == 1 && !visited[i] ) {
                    visited[i] = true; // 전염표시(방문표시)
                    queue.add(i); // BFS를 위해 큐에 데이터 저장
                    count++; // 전염시켰으므로 counting!
                }
            }
        }
 
        System.out.println(count);
 
    }
}