[JAVA/2606번] 바이러스

문제

입력 및 출력

풀이

import java.io.*;
import java.util.*;

class Main {
    public static int N;
    public static int K;
    public static int[][] graph;
    public static boolean[] visited;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N = 컴퓨터의 수
        N = Integer.parseInt(br.readLine());

        // K = 네트워크상에서 직접 연결되어있는 컴퓨터의 수
        K = Integer.parseInt(br.readLine());

        // 그래프 데이터 크기
        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < K; i++) {
            String[] temp = br.readLine().split(" ");
            int one = Integer.parseInt(temp[0]);
            int two = Integer.parseInt(temp[1]);
            graph[one][two] = 1;
            graph[two][one] = 1;
        }

        // BFS메소드 호출
        BFS();
    }
    public static void BFS() {
        Queue < Integer > queue = new LinkedList < > ();

        // 1번 컴퓨터가 웜 바이러스에 걸렸으므로 방문했음을 표시
        queue.add(1);
        visited[1] = true;

        // 바이러스에 걸린 컴퓨터의 수
        int count = 0;
        while (!queue.isEmpty()) {
            // 큐의 가장 앞에 있는 원소를 추출
            int node = queue.poll();

            for (int i = 1; i < N + 1; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법
1번 접점과 연결되어 있는 모든 접점을 감염시키고, 감염된 갯수를 화면에 출력하면 풀리는 간단한 문제였다.

이전에 풀었던 문제와 다른점이라면 그래프이기 때문에 1에서 2로 연결되는 경우와 2에서 1로 연결되는 경우를 같이 처리해주어야 하는 점이다.

이번 문제는 무조건 1번이 감염되었다는 정의가 있기 때문에 1번에서 출발하여 연결되어 있는 모든 정점을 방문했을 경우 방문했던 정점의 개수를 결과 값으로 출력한다.