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

문제

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

2606번: 바이러스

코드

using System;

class Algorithm
{
    static int n, m;
    static List<int>[] computers;
    static bool[] visited;
    static void Main(string[] arg)
    {
        int n = int.Parse(Console.ReadLine()); // com 총 수
        int m = int.Parse(Console.ReadLine()); // 연결된 수

        computers = new List<int>[n+1];

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

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

            computers[a].Add(b);
            computers[b].Add(a); // 양방향 연결
        }

        visited = new bool[n+1];

        BFS(computers, visited, 1); // 연결 정보, 방문 정보, 시작점
        
        int cnt = 0;
        
        for(int i = 2; i <= n; i++)
        {
            if(visited[i] == true)
            {
                cnt++;
            }
        }
        
        Console.WriteLine(cnt);

    }

    static void BFS(List<int>[] computers, bool[] visited, int start)
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        visited[start] = true;

        while(queue.Count > 0)
        {
            int target = queue.Dequeue();

            foreach(int i in computers[target])
            {
                if(!visited[i])
                {
                    queue.Enqueue(i);
                    visited[i] = true;
                }
            }

        }
    }
}

고민

1. 양방향 매핑을 해줬다. 배열에 리스트를 담은 모습이니 { List<int>, List<int>, List<int> ... } 이런 느낌으로 담겼을듯

2. BFS를 연습중이라 BFS로 돌렸다. 리스트, 방문여부, 시작점을 매개변수로 담기

3. BFS에서는 Queue에 담고 Queue에 관련된 녀석들 찾아내고 방문 체크하고 방문 안했으면 Queue에 또 담고... 이렇게 건너건너 내부자를 색출했다.

4. 이 문제 함정이 있다. 바로 1번이 감염시킨 컴퓨터의 수다. 그러니 1번을 제외한 1번에게 감염당한 컴퓨터 수를 카운트 해야한다. 그리서 BFS가 끝난 뒤 for문에서 i=2인것이다...