[Java] 2606 바이러스 - BFS

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

2606번: 바이러스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int V, E, answer;
    static boolean[] visit;
    static List<List<Integer>> list;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());
 
        visit = new boolean[V+1];
        list = new ArrayList<>();
        for(int i=0;i<=V;i++){
            list.add(new ArrayList<>());
        }
 
        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
 
            list.get(to).add(from);
            list.get(from).add(to);
        }
 
        answer = bfs(1);
 
        System.out.println(answer);
    }
 
    public static int bfs(int x){
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visit[x] = true;
 
        while (!queue.isEmpty()){
            int c = queue.poll();
 
            for(int i=0;i<list.get(c).size();i++){
                int n = list.get(c).get(i);
                if(!visit[n]){
                    visit[n] = true;
                    queue.add(n);
                    count++;
                }
 
            }
        }
        return count;
    }
 
}
 

[풀이]

 

이중 중첩 리스트를 사용하였다.

따라서 필요 Node에 연결된 Node의 개수만큼 반복문을 돌릴 수 있었고,

1번 노드와 연결된 노드들을 찾아 정답으로 출력해주었다.

 

끄읕