백준 2606. 바이러스 :: 돼지개발자

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

"BFS"

해당 문제는 정말 단순한 BFS 문제이다. 1번 노드를 시작으로 연결된 모든 노드들의 개수를 세면 된다. 먼저 주어진 정보를 

토대로 인접행렬 adj를 만든다. 그후 BFS 에 따라 queue 에 연결된 노드들을 하나씩 넣어주고 탐색한다.

간단하다. 

1번 노드는 세지 카운트 하지 않음을 주의한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int N,M;
    static int[][] adj;
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();
    
    public static void main (String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        
        adj = new int[N+1][N+1];
        visited = new boolean [N+1];
        
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            adj[a][b] = adj[b][a] = 1;
        }
        
        visited [1] = true;
        q.add(1);
        int res = -1;
        
        while(!q.isEmpty()) {
            
            int cur = q.poll();
            res ++;
            for (int i = 1; i <= N; i++) {
                if(visited[i] || adj[cur][i] == 0) 
                    continue;
                
                visited[i] = true;
                q.add(i);
            }
        }
        System.out.println(res);
    }
 
}