[백준/java] 2606번 - 바이러스

- 분류 : DFS/BFS

 

- 문제 : https://www.acmicpc.net/problem/2606

 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Computer {
    int num;//컴퓨터 번호
    boolean marked;//방문 여부
    LinkedList<Computer> adjacent;
 
    Computer(int num) {
        this.num = num;
        this.marked = false;
        this.adjacent = new LinkedList<>();
    }
}
 
class Graph {
    Computer[] computers;
    int count; //바이러스에 감염된 컴퓨터 수
 
    Graph(int size) {
        this.computers = new Computer[size];
        for (int i = 0; i < size; i++) {
            computers[i] = new Computer(i + 1);
        }
        count = 0;
    }
 
    void addEdge(int i1, int i2) {
        Computer c1 = computers[i1 - 1];
        Computer c2 = computers[i2 - 1];
        if (!c1.adjacent.contains(c2)) {
            c1.adjacent.add(c2);
        }
        if (!c2.adjacent.contains(c1)) {
            c2.adjacent.add(c1);
        }
    }
 
    void bfs() {
        Queue<Computer> queue = new LinkedList<>();
        Computer root = computers[0];
        root.marked = true;
        queue.add(root);
 
        while (!queue.isEmpty()) {
            Computer computer = queue.poll();
            for (Computer c : computer.adjacent) {
                if (c.marked == false) {
                    c.marked = true;
                    queue.add(c);
                }
            }
            visit(computer);
        }
    }
 
    void visit(Computer computer) {
        if (computer.num != 1) {
            count += 1;
        }
    }
}
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        sc.nextLine();
        int edges = sc.nextInt();
        sc.nextLine();
        Graph g = new Graph(size);
        for (int i = 0; i < edges; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g.addEdge(a, b);
            sc.nextLine();
        }
 
        g.bfs();
        System.out.print(g.count);
    }
}