[알고리즘] 백준 2606번 바이러스 :: 우유

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

 

백준 2606번: 바이러스 (Java) - DFS & ArrayList로 그래프 구현하기

---

📌 문제 개요

1번 컴퓨터가 바이러스에 걸렸다.
직접 연결된 컴퓨터를 통해 감염이 퍼질 수 있다.
감염된 컴퓨터의 총 수를 구하자. (단, 1번은 감염됐지만 제외)

---

💡 문제 유형

• 그래프 탐색
• DFS(깊이 우선 탐색)
• 인접 리스트 방식으로 그래프 구현

---

🧠 핵심 개념 정리

✅ 그래프(Graph)

• 정점(Node)과 간선(Edge)으로 이루어진 자료구조
• 이 문제에선 컴퓨터 = 정점, 연결 = 간선

✅ DFS (Depth-First Search)

• 깊이 우선 탐색
• 한 방향으로 계속 탐색하다가 더 이상 갈 곳이 없으면 되돌아감
• 재귀(Recursive) 방식으로 구현 가능

✅ 인접 리스트 (Adjacency List)

• 정점을 배열로 선언하고, 각 인덱스에 연결된 노드들을 리스트로 저장
• 자바에서는 ArrayList<ArrayList<Integer>> 형태로 구성

 

---

💻 코드 설명 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;
    static int cnt = 0;

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

        N = Integer.parseInt(br.readLine());    // 컴퓨터 수
        M = Integer.parseInt(br.readLine());    // 연결 수

        visited = new boolean[N + 1];           // 방문 배열
        graph = new ArrayList<>();

        // 인접 리스트 초기화
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);    // 양방향 연결
            graph.get(b).add(a);
        }

        DFS(1); // 1번 컴퓨터에서 시작

        System.out.println(cnt - 1); // 자기 자신 제외
    }

    // DFS 함수
    static void DFS(int V) {
        visited[V] = true;
        cnt++;

        for (int next : graph.get(V)) {
            if (!visited[next]) {
                DFS(next);
            }
        }
    }
}

---

🧩 코드 분석 포인트

구문설명

graph = new ArrayList<>();	전체 그래프 초기화
graph.add(new ArrayList<>());	각 정점에 대한 연결 리스트 초기화
DFS(int V)	깊이 우선 탐색 함수
visited[]	중복 방문 방지용 boolean 배열
cnt - 1	감염된 컴퓨터 수에서 1번 제외

 

---

📝 마무리 정리

• DFS는 연결된 모든 노드를 빠짐없이 탐색하는 데 유용
• ArrayList를 이용한 인접 리스트 구성은 메모리 효율적
• 1번 컴퓨터를 기준으로 연결된 컴퓨터를 모두 탐색 후, 개수만 세면 해결