[백준] 2606번: 바이러스 (Java)

1. 문제설명

한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 감염된다. 1번 컴퓨터가 웜 바이러스에 걸렀을 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

⇒ 네트워크 연결 → DFS

• 노드의 수와 간선 정보를 인접행렬로 저장한다.
• 방문 체크할 visited 배열을 생성한다.
• 재귀 호출하는 메서드를 통해 1번과 연결된 컴퓨터를 찾는다.
  • 탐색할 노드 번호(row)를 매개변수로 받는다.
  • 행렬에서 해당 row를 탐색하며 col이 1이고, 방문하지 않은 경우
    • count 1 증가 (결과값)
    • 해당 col로 재귀 호출

 

3. 최종 코드

import java.io.*;

public class Main {
    static int n, e;
    static int[][] adjMatrix; // 인접 행렬
    static boolean[] visited; // 방문 여부 체크
    static int count = 0; // 감염된 컴퓨터 수 (결과값)

    static void dfs(int s) {
        visited[s] = true; // 현재 노드 방문 처리

        for(int i=1; i<=n; i++) {
            // 현재 컴퓨터와 연결되어 있고, 아직 방문하지 않은 경우
            if(adjMatrix[s][i] == 1 && !visited[i]){
                count++; // 결과값 증가
                dfs(i); // 해당 컴퓨터로 재귀 호출
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        e = Integer.parseInt(br.readLine());
        adjMatrix = new int[n+1][n+1];
        visited = new boolean[n+1];
        for(int i=0; i<e; i++) {
            String[] edge = br.readLine().split(" ");
            int u = Integer.parseInt(edge[0]);
            int v = Integer.parseInt(edge[1]);
            // 무방향 그래프 -> 양쪽 모두 1로 설정
            adjMatrix[u][v] = 1;
            adjMatrix[v][u] = 1;
        }

        dfs(1); // 1부터 DFS 시작
        System.out.println(count);
    }
}

 

4. 시간복잡도

• DFS: 컴퓨터의 수가 N일 때 $O(N^2)$
• 간선 정보 입력: 간선의 수가 E일 때 $O(E)$

따라서 전체 시간복잡도는 $O(N^2 + E)$