백준 2606번 바이러스 (C#)

김보근·2025년 8월 6일

C#백준

백준

목록 보기

56/62

백준 2606번 C바이러스 문제 풀이

오늘은 백준 2606번 바이러스 문제를 풀어봤다.
DFS 기본 개념을 잘 활용하는 문제였고, 덕분에 그래프 탐색에 대해 좀 더 감을 잡을 수 있었다.

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

문제 설명

한 컴퓨터가 바이러스에 걸리면 연결된 모든 컴퓨터들도 감염된다.
1번 컴퓨터가 바이러스에 걸렸을 때,
1번 컴퓨터를 통해 감염되는 컴퓨터 수(1번 제외)를 구하는 문제.

문제 접근 방식

문제는 무방향 그래프 형태로 주어진다.
입력으로 네트워크 연결 정보가 주어지는데, 이를 인접 리스트로 표현했다.
DFS를 이용해서 1번 컴퓨터에서 시작해 연결된 모든 컴퓨터를 방문하고, 감염된 컴퓨터 수를 세면 된다.
중요한 건, 1번 컴퓨터와 연결되지 않은 컴퓨터는 감염되지 않는다는 점이다.

예시 입력

이걸 인접 리스트로 만들면:

graph[1] = [2, 5]  
graph[2] = [1, 3, 5]  
graph[3] = [2]  
graph[4] = [7]  
graph[5] = [1, 2, 6]  
graph[6] = [5]  
graph[7] = [4]

DFS(1)을 하면 연결된 컴퓨터는 2, 3, 5, 6 → 총 4개가 감염된다.

예외 상황

입력에 이런 경우가 있다고 가정하자:

여기서 5-7은 1번과 연결된 경로가 없기 때문에 감염되지 않는다.
이걸 그래프 연결 요소라고 하는데, 5-7은 1번과 다른 연결 요소에 속해 있는 것이다.

작성한 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {
        static List<int>[] graph;
        static bool[] visited;
        static int infectedCount = 0;
       
        static void Main()
        {
            int n = int.Parse(Console.ReadLine()); // 컴퓨터 수
            int m = int.Parse(Console.ReadLine()); // 연결된 쌍 수

            graph = new List<int>[n + 1];
            visited = new bool[n + 1];

            for (int i = 0; i <= n; i++)
            {
                graph[i] = new List<int>();
            }

            for (int i = 0; i < m; i++)
            {
                string[] input = Console.ReadLine().Split();
                int a = int.Parse(input[0]);
                int b = int.Parse(input[1]);

                graph[a].Add(b);
                graph[b].Add(a);
            }

            DFS(1);

            Console.WriteLine(infectedCount);
        }

        static void DFS(int node)
        {
            visited[node] = true;

            foreach (int neighbor in graph[node])
            {
                if (!visited[neighbor])
                {
                    infectedCount++;
                    DFS(neighbor);
                }
            }
        }
    }
}