[백준 JAVA] 2606 바이러스

2606 바이러스

https://www.acmicpc.net/problem/2606

문제설명

 

• 네트워크에 연결된 컴퓨터들이 있으며, 컴퓨터 1번에서 시작하여 웜 바이러스가 퍼진다고 가정할 때,
• 컴퓨터 1번으로부터 영향을 받는 다른 컴퓨터의 수를 구한다.

 

접근방식

O(n + m)  DFS 탐색 시간복잡도

• 각 노드를 스택에서 한 번 꺼내고, 해당 노드의 모든 인접 노드에 대해 스택에 추가하는 과정을 반복한다.
  
  • 여기서 V는 노드의 수 (컴퓨터의 수, 즉 n)
  • E는 엣지의 수 (네트워크 상의 연결 쌍의 수, 즉 m)
  • DFS 탐색의 시간 복잡도는 O(n + m) 시간이 소요된다.

문제 조건 분석 과정

 

 

그래프를 인접 리스트로 구성한다. 각 컴퓨터(노드)에 대해 연결된 리스트를 초기화한다.

m개의 연결 쌍을 읽어 그래프에 추가한다. 각 쌍 (a, b)에 대해 두 리스트에 연결을 추가한다.

 

전체코드

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

public class Main {

    // 그래프를 인접 리스트로 표현
    private static List<List<Integer>> g;
    // 각 노드의 방문 여부를 체크할 배열
    private static boolean[] v;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine().trim()); //총 컴퓨터의 수
        int m = Integer.parseInt(br.readLine().trim()); //네트워크에 연결된 컴퓨터의 쌍

        // 그래프 초기화: 각 컴퓨터를 노드로 하는 리스트 생성
        g = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }

        // 네트워크 상에서 연결된 컴퓨터 쌍의 수만큼 반복하여 그래프 구성
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 양방향 그래프이므로 a와 b를 서로 연결
            g.get(a).add(b);
            g.get(b).add(a);
        }

        v = new boolean[n + 1];

        // DFS를 사용한 1번 컴퓨터에서 시작하여 바이러스가 퍼지는 컴퓨터 수
        int result = dfs(1) - 1; // 1번 컴퓨터를 제외한 나머지 컴퓨터 수

        // 결과를 출력합니다.
        System.out.println(result);
    }

    // DFS 메서드
    private static int dfs(int start) {
        // DFS를 위한 스택 초기화
        Stack<Integer> stack = new Stack<>();
        stack.push(start); // 시작 노드를 스택에 푸시
        int count = 0; // 방문한 노드의 수를 세기 위한 변수

        // 스택이 비어있지 않을 때까지 반복
        while (!stack.isEmpty()) {
            int node = stack.pop(); // 스택에서 노드 꺼내기
            // 노드가 아직 방문되지 않았다면
            if (!v[node]) {
                v[node] = true; // 노드를 방문 처리
                count++; // 방문한 노드 수 증가
                // 현재 노드와 연결된 모든 노드를 스택에 추가
                for (int neighbor : g.get(node)) {
                    if (!v[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        return count; // 탐색을 통해 방문한 총 노드 수 반환
    }
}