[백준] 2606 바이러스(BFS)

 

 

소스 해석

• int graph[][] 배열을 만들어주고, 값을 할당
• boolean check[] 배열을 만들어주고, 값을 할당
• queue를 활용하여 graph를 탐색 시작 
• 1부터 주어진 값까지 순회하기 위해 for 문을 활용하고 
  for문에서는 방문하지 않았고, 이동 가능한 graph가 있는지 확인을 진행
• 이동 가능한 graph가 있으면 queue에 값을 넣어주고, visited[]를 true로 처리해줌.

 

package Baekjoon;

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

public class BOK_2606 {
    static int[][] graph;
    static boolean[] check;
    static int max;
    static int count;
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        max = Integer.parseInt(br.readLine());
        int num = Integer.parseInt(br.readLine());
        graph = new int[max+1][max+1];
        check = new boolean[max+1];
        for(int i=0; i<num; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken());
            graph[a1][a2] = graph[a2][a1] = 1;
        }
        bfs(1);
    }
    public static void bfs(int n){
        Queue<Integer> queue = new LinkedList();
        queue.add(n);

        while(!queue.isEmpty()){
            int x = queue.poll();
            check[x] = true;
            for(int i=1; i<max+1; i++){
                if(!check[i] && graph[x][i] == 1){
                    check[i] = true;
                    queue.add(i);
                    count++;
                }
            }
        }
    }
    public static void main(String[] args) {

    }
}