[백준2606/java] 바이러스

- 알고리즘 분류 : DFS/BFS

 

나는 BFS를 이용해서 풀었다.

 

• 1번 컴퓨터가 바이러스에 걸렸을 때 감염된 컴퓨터 수를 구하라.
• DFS, BFS 둘다 사용 가능하지만, 일단 인접한 컴퓨터를 기준으로 먼저 탐색할 것이기 때문에 나는 BFS를 이용해서 풀었다.
• 1번 컴퓨터(root)를 시작으로 인접한 컴퓨터들부터 순차적으로 방문한다. 방문한 컴퓨터들은 연결되어있다는 뜻이므로 “감염된 컴퓨터의 수 = 방문한 컴퓨터의 수”가 된다.

 

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]; // 1번 컴퓨터
        root.marked = true;
        queue.add(root);

        while (!queue.isEmpty()) {
						//queue에 들어있는 컴퓨터 꺼내서 방문
            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) {
				// 1번컴퓨터 제외
        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);
    }
}