[BFS] 백준 2606 바이러스

[BFS] 백준 2606 바이러스 

[문제 출처] 

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

* BFS에 대한 개념

BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 자료 구조 Queue를 사용하는 경우가 일반적이다. 배열에서 사용하는 경우, 방향 데이터를 이용해 배열의 시작점에서 범위를 넖혀 가면서 탐색하는 것이다.

[참조] https://namu.wiki/w/BFS

* Queue의 이용

[참조] https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

[풀이과정]

양방향을 꼭 체크해주어야 한다. 이 부분을 놓친다!!!!

[코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class q2 {
        
        static int num, connect;
        static int com1, com2;
        
        static BufferedReader br;
        static BufferedWriter bw;
        
        static StringTokenizer st;
    
    public static void main(String[] args) throws IOException{
        
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        num = Integer.parseInt(br.readLine());
        connect = Integer.parseInt(br.readLine());
        
        ArrayList<ArrayList<Integer>> networks = new ArrayList<>();
        
        for(int i=0;i<=num;i++) {
            networks.add(new ArrayList<>());
        }
        
        for (int i=0;i<connect;i++) {
            st = new StringTokenizer(br.readLine());
            com1 = Integer.parseInt(st.nextToken());
            com2 = Integer.parseInt(st.nextToken());
            
            networks.get(com1).add(com2);
            networks.get(com2).add(com1);
        }
        
        Bfs bfs = new Bfs(networks);
        System.out.println(bfs.virusCount());
    }
    
    static class Bfs {
        ArrayList<ArrayList<Integer>> networks = new ArrayList<>();
        
        public Bfs(ArrayList<ArrayList<Integer>> networks) {
            this.networks = networks;
        }
        
        public int virusCount() {
            int count = 0;
            boolean[] visited = new boolean[networks.size()];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(1);
            visited[1] = true;
            while(!queue.isEmpty()) {
                int computer = queue.poll();
 
                ArrayList<Integer> infections = networks.get(computer);
                for (int i=0;i<infections.size();i++) {
                    if(!visited[infections.get(i)]) {
                        count++; 
                        queue.offer(infections.get(i));
                        visited[infections.get(i)]=true;
                    }
                }
            }
        
            return count;
        }
        
    }
 
}