[백준] 2606 바이러스 | DFS, BFS, 그래프 | 실버 Ⅲ | JAVA

📌 문제

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

 

⭐ 문제 분석

1. 그래프 모델링
   • 각 컴퓨터를 노드로 보고, 두 컴퓨터 간의 연결을 엣지로 표현합니다.
   • 연결 관계를 기반으로 무방향 그래프를 구성합니다.
2. 문제 요구 사항
   • 1번 컴퓨터에서 시작하여 바이러스가 전파될 수 있는 모든 컴퓨터의 개수를 계산합니다.
   • 방문한 노드를 추적하면서 연결된 모든 컴퓨터를 탐색합니다.
3. 알고리즘
   • 그래프 탐색 알고리즘인 DFS(깊이 우선 탐색) 또는 **BFS(너비 우선 탐색)**를 사용합니다.

 

⭐ 해결 방법

1. 입력 처리
   • 첫 줄에서 컴퓨터의 개수를 입력받습니다.
   • 두 번째 줄에서 연결 정보의 개수를 입력받고, 이후 줄에서 연결된 노드 정보를 처리합니다.
2. 그래프 구현
   • ArrayList를 이용하여 인접 리스트 형태로 그래프를 구성합니다.
3. 그래프 탐색
   • 1번 컴퓨터에서 시작하여 DFS 또는 BFS로 연결된 모든 컴퓨터를 탐색합니다.
   • 탐색 중 방문한 컴퓨터의 개수를 카운트합니다.
4. 결과 출력
   • 1번 컴퓨터를 제외한 바이러스 전파된 컴퓨터 수를 출력합니다.

 

✅ 정답 코드

import java.util.*;

public class Virus {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 컴퓨터 수
        int m = scanner.nextInt(); // 연결 수

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 입력
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 방문 배열
        boolean[] visited = new boolean[n + 1];

        // DFS 탐색
        int result = dfs(1, graph, visited);

        // 1번 컴퓨터는 제외하고 출력
        System.out.println(result - 1);
    }

    private static int dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        int count = 1; // 현재 노드 포함

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                count += dfs(next, graph, visited);
            }
        }

        return count;
    }
}

🗒️ 코드 설명

1. 입력 처리
   • Scanner를 사용하여 컴퓨터 수와 연결 관계를 입력받습니다.
   • ArrayList를 활용해 그래프를 인접 리스트로 저장합니다.
2. DFS 탐색
   • dfs 메서드를 재귀적으로 호출하여 방문한 노드를 추적합니다.
   • 방문한 노드 수를 반환하며, 연결된 모든 노드를 탐색합니다.
3. 결과 출력
   • 1번 컴퓨터에서 시작한 바이러스 전파 결과에서 1번 컴퓨터를 제외한 수를 출력합니다.

 

💡 알고리즘 풀이 방법

1. 그래프 생성
   • 연결 정보를 기반으로 인접 리스트를 생성합니다.
2. DFS 탐색
   • 1번 컴퓨터를 시작점으로 설정하고, 연결된 모든 노드를 탐색하며 방문합니다.
   • 방문한 노드를 visited 배열로 관리합니다.
3. 시간 복잡도
   • 그래프의 모든 노드를 탐색하므로 O(V + E) (노드 수 + 간선 수)입니다.