boj 2606 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

처음에 1번 컴퓨터가 바이러스에 걸리고 이 컴퓨터로 인해 바이러스에 걸리는 컴퓨터가 몇 대인지 출력하는 문제입니다.

 

이 문제는 간단한 bfs로 해결할 수 있습니다.

입력으로 u와 v가 주어지면 둘이 연결되어있다는 말입니다.

이 그래프는 양방향 그래프이기 때문에 u의 간선에도 v를 추가하고, v의 간선에도 u를 추가해야합니다.

 

그 다음 1번부터 시작하여 bfs로 연결되어있는 컴퓨터 수를 구하시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> list[];
    static boolean visit[];
    static int N, M, ans;
 
    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visit[1] = true;
        while (!q.isEmpty()) {
            int v = q.peek();
 
            q.remove();
 
            for (int i = 0; i < list[v].size(); i++) {
                int next = list[v].get(i);
 
                if (visit[next])
                    continue;
 
                q.add(next);
                visit[next] = true;
                ans++;
            }
        }
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            list[u].add(v);
            list[v].add(u);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
        System.out.println(ans);
    }
}