[백준 2606:바이러스]Java, bfs

bfs를 이용해서 푼 코드입니다.

1. 행렬로 네트워크를 나타내어 줍니다.

2. bfs(1)을 합니다. 시작노드를 큐에 넣고 이어진 그래프를 탐색하게 됩니다.

탐색하는 과정은

큐에 데이터가 있으면 dequeue해서 이전에 큐에 넣었던 노드와

현재 탐색 중인 노드가 연결되어 있는지 체크하게 됩니다.

package mnth_11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class BJ2606_BFS {
 
        static int N_com, N_conn;
        static int map[][];
        static int cnt;
        static int visited[];
        static Queue<Integer> q = new LinkedList<Integer>();
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            
            Scanner scan = new Scanner(System.in);
            
            N_com = scan.nextInt();
            N_conn = scan.nextInt();
            
            map = new int[N_com+1][N_com+1];
            visited = new int[N_com+1];
            
            for(int i=0;i<N_conn;i++) 
            {
                int a = scan.nextInt();
                int b = scan.nextInt();
                map[a][b] = map[b][a] = 1;    
            }
            
            bfs(1);
            System.out.println(cnt);
        }
        static void bfs(int start) 
        {
            
            q.offer(start);
            visited[start] = 1;
            
            while(q.isEmpty() == false) 
            {
                int current = q.poll();
                
                for(int i=1;i<N_com+1;i++)
                {
                    if(map[current][i] == 1 && visited[i] == 0)
                    {
                        q.offer(i);
                        visited[i] = 1;
                        cnt++;
                    }
                }
            }
        }
    }