[Baekjoon Online Judge] 2606번: 바이러스

2606번: 바이러스

요구사항

 - 바이러스는 네트워크를 통해 전파된다.

 - 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에 연결되어 있는 모든 컴퓨터는 바이러스에 걸린다.

입력

 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

 

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon2606 {

    static int[][] matrix;
    static boolean[] visited;
    static int v, e;
    static int count = 0;

    public static void bfs(int start) throws IOException {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            ++count;

            for (int i = 0; i < matrix.length; i++) {
                if (matrix[vertex][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void print() {
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        v = Integer.parseInt(bufferedReader.readLine());
        e = Integer.parseInt(bufferedReader.readLine());

        matrix = new int[v + 1][v + 1];
        visited = new boolean[v + 1];

        for (int i = 1; i <= e; i++) {
            String[] vertices = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(vertices[0]);
            int y = Integer.parseInt(vertices[1]);

            matrix[x][y] = 1;
            matrix[y][x] = 1;
        }

        print(); // 값이 잘 들어 갔는지 확인
        bfs(1);
        bufferedWriter.write(String.valueOf(count - 1));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 간선을 연결하는 정점들을 인접 행렬로 구현한다. 1번 컴퓨터 탐색하기 때문에 1번부터 bfs를 실행한다. 큐에서 값을 꺼내올 때 마다 컴퓨터가 감염되었다고 가정한다. 1번 컴퓨터는 이미 걸려있기 때문에 값을 출력할 때 -1을 사용한다.