[백준] 2606번: 바이러스 [C#]

 

dfs던 bfs던 아무 그래프 순회 알고리즘을 사용하여 1번 정점으로부터 방문 가능한 모든 정점의 개수를 요구하는 문제이다.

주의해야 할 점은 '1번 컴퓨터' 로 부터 감염될 수 있는 컴퓨터의 수를 구하는 문제이기 때문에, 1번 정점은 빼주고 개수를 구해주어야 한다.

 

using System.Collections.Generic;
 
namespace real연습
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int edges = int.Parse(Console.ReadLine());
            int linkes = int.Parse(Console.ReadLine());
            Graph graph = new Graph(edges);
 
            for (int i = 0; i < linkes; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph.graph[input[0]].Add(input[1]);
                graph.graph[input[1]].Add(input[0]);
            }
            int result = 0;
            result = dfs_search(graph);
            Console.WriteLine(result);
        }
        static int dfs_search(Graph graph)
        {
            int result = 0;
 
            Stack<int> stack = new Stack<int>();
            stack.Push(1);
            List<int> visited = new List<int>();
            
            while (stack.Count != 0)
            {
                int current = stack.Pop();
 
                if (visited.Contains(current) == false)
                {
                    if (current != 1)
                    {
                        result++;
                    }
                    visited.Add(current);
                }
                for (int i = graph.graph[current].Count - 1; i >= 0; i--)
                {
                    if (visited.Contains(graph.graph[current][i]) == false)
                    {
                        stack.Push(graph.graph[current][i]);
                    }
                }
            }
 
            return result;
        }
        private class Graph
        {
            int _size;
            public List<int>[] graph;
            public Graph(int size)
            {
                this._size = size;
                this.graph = new List<int>[_size + 1];
                for (int i = 1; i <= _size; i++)
                {
                    graph[i] = new List<int>();
                }
            }
        }
    }
}