문제 출처

단계별로 풀어보기 > 그래프와 순회 > 바이러스
https://www.acmicpc.net/problem/2606

문제 설명

웜 바이러스는 네트워크가 연결 된 컴퓨터끼리 감염된다.
컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리는 컴퓨터의 수를 출력하라.

접근 방법

주어진 정보를 통해 양방향 그래프를 생성한다.
이후, BFS에 1번 컴퓨터를 집어 넣어서 어떤 컴퓨터들이 감염되었는지 확인한다.
1번을 제외한 컴퓨터 수를 출력해야하므로, 감염된 컴퓨터(visited)를 확인할 땐, 2번부터 시작한다.

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

public class 바이러스 {
    static int[] visited;
    static int[][] graph;

    public static void bfs(int s){
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        visited[s] = 1;

        while(!q.isEmpty()){
            int n = q.poll();

            for(int i = 1; i < graph.length; i++){
                if(visited[i] == 0 && graph[n][i] == 1){
                    q.add(i);
                    visited[i] = 1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        visited = new int[N+1];
        graph = new int[N+1][N+1];

        StringTokenizer st;

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());

            int k = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());

            graph[k][l] = 1;
            graph[l][k] = 1;
        }

        bfs(1);

        int count = 0;
        for(int i = 2; i < N+1; i++){
            if(visited[i] == 1) count++;
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

해당 풀이의 시간 복잡도는 O(N^2)이다. 이는 인접 행렬 방식으로 풀어서 그렇다.
하지만, 인접 리스트 방식으로 풀면 O(N + e) (노드 + 간선)으로 풀 수 있음을 알게되었다.
주어진 문제에서 N의 크기가 작으면 인접 행렬 방식으로 풀 수 있지만, N이 크게 되면 해당 방식으로 풀지 못하고, 인접 리스트 방식으로 풀어야한다.

문제푼 흔적