[C#] 백준 2606번 문제풀이

문제번호: 2606

문제명: 바이러스

문제링크: https://www.acmicpc.net/problem/2606

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

오늘은 그래프 탐색 문제인 '바이러스'문제를 풀었습니다. DFS를 이용하여 전파된 컴퓨터들의 수를 카운트하고 마지막에 출력시켜주었습니다. DFS는 visited배열로 방문 유무를 체크하여 기존 방문했던 노드를 다시 방문하지 않도록 구현하였습니다.
다음은 정답코드입니다.

public static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int n = int.Parse(sr.ReadLine()); // 7
    int ssang = int.Parse(sr.ReadLine()); // 6

    List<int>[] array = new List<int>[n]; // 0 ~ 6
    bool[] visited = new bool[n];
    int infectedComputerCount = 0;

    for (int i = 0; i < n; i++)
    {
        array[i] = new List<int>();
    }
    for (int i = 0; i < ssang; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        int a = input[0];
        int b = input[1];

        array[a - 1].Add(b - 1);
        array[b - 1].Add(a - 1);
    }

    DFS(0);
    void DFS(int depth)
    {
        if (visited[depth]) return;

        visited[depth] = true;
        infectedComputerCount++;
        foreach (int computer in array[depth])
        {
            DFS(computer);
        }
    }

    sw.WriteLine(infectedComputerCount -1);

    sr.Close();
    sw.Close();
}