[JAVA]백준_2606_바이러스

문제링크

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

2606번: 바이러스

 

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_2606 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int map[][] = new int[N+1][N+1];

        for(int i=0;i<M;i++){
            String temp[] = br.readLine().split(" ");
            int a = Integer.parseInt(temp[0]);
            int b = Integer.parseInt(temp[1]);

            map[a][b] = 1;
            map[b][a] = 1;
        }

        //for(int i=1;i<=N;i++) System.out.println(Arrays.toString(map[i]));
        System.out.println(bfs(map,1,N));
    }

    private static int bfs(int[][] map, int i, int N) {
        //연결되어있는 모든 애들 찾기
        Queue<Integer> q = new LinkedList<>();
        boolean isVisited[] = new boolean[N + 1];
        int result = 0;
        q.offer(1);
        isVisited[1] = true;

        while(!q.isEmpty()){
            int number = q.poll();

            for(int n=1;n<=N;n++){
                if(map[number][n] ==1 && !isVisited[n]){
                    q.offer(n);
                    isVisited[n] = true;
                    result++;
                }
            }
        }

        return result;
    }
}