2606번 바이러스

코딩테스트 : 2606번 바이러스 

바이러스 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

219089

105042

69229

46.422%

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

public class BackJoon
{
    public static void Main()
    {
        int number = int.Parse(Console.ReadLine());
        int channel = int.Parse(Console.ReadLine());
        
        bool[] isUsed = new bool[number+1];
        isUsed[0] = false;

        //   Dictionary<int, List<int>> numbers = new Dictionary<int, List<int>>();
        //
        //   for (int i = 0; i < channel; i++)
        //   {
        //       int[] current = Console.ReadLine().Split().Select(int.Parse).ToArray();
        //       if (numbers.ContainsKey(current[0]))
        //       {
        //           numbers[current[0]].Add(current[1]);
        //       }
        //       else
        //       {
        //           numbers.Add(current[0], new List<int> { current[1] });
        //       }
        //       
        //   }
        // }
        
        
        List<(int,int)> channels = new List<(int,int)>();

        for (int i = 0; i < channel; i++)
        {
            int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (numbers[1] < numbers[0])
            {
                int n = numbers[0];
                numbers[0] = numbers[1];
                numbers[1] = n;
            }
            channels.Add((numbers[0], numbers[1]));
        }
        
        channels.Sort();
        isUsed[1] = true;
        for (int i = 0; i < channels.Count; i++)
        {
            if (isUsed[channels[i].Item1])
            {
                isUsed[channels[i].Item2] = true;
            }
        }

        int count = 0;
        for (int i = 0; i < isUsed.Length; i++)
        {
            if (isUsed[i]) count++;
        }
        
        Console.WriteLine(count - 1);
    }


}

 

 

1번 생각 : 정렬해서 순서대로 연결을 따라가면 되지 않을까 생각했다. 하지만 이 방식은 양방향 연결을 고려하지 못한다. 예를 들어 (1, 3)과 (3, 1)은 같은 연결이지만, 정렬 후 순서대로만 탐색한다면 한쪽 방향만 탐색되어 전파가 누락될 수 있다.
예를 들어 , ( 1,  3 ) 과 ( 3 , 1 )은 같은 연결이지만, 정렬해서 순서대로 바이러스를 전파하게 된다면 전자는 전파가 가능하지만 후자는 되지 않는다. 

2번 생각 : 그렇다면 정렬하기 전에 연결을 추가할 때 번호가 더 작은 컴퓨터가 앞에 오도록 앞뒤를 바꿔 저장하면 괜찮지 않을까 생각했다. 즉, 모든 전파가 낮은 번호에서 높은 번호로만 가도록 하면 위와 같은 문제가 해결될 것 같았다.
그래서 숫자 스왑 방식을 시도했다. 하지만 이 방법으로는 1번과 7번이 연결되어 있고, 2번과 7번이 연결되어 있어도 1번과 2번 사이가 직접 연결되어 있지 않으면 올바르게 바이러스를 전파할 수 없는 문제가 있었다. 즉, 간접적인 연결을 제대로 처리하지 못했다.

3번 생각 : 결국 DFS로 푸는 것이 가장 적절하다고 판단했다.

public class BackJoon
{
    public static void Main()
    {
        int number = int.Parse(Console.ReadLine());
        int channel = int.Parse(Console.ReadLine());
        
        bool[] isUsed = new bool[number+1];
        isUsed[0] = false;

       Dictionary<int, List<int>> numbers = new Dictionary<int, List<int>>();

       for (int i = 0; i < channel; i++)
       {
           int[] currentNumbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
           if (numbers.ContainsKey(currentNumbers[0]))
           {
               numbers[currentNumbers[0]].Add(currentNumbers[1]);
           }
           else
           {
               numbers.Add(currentNumbers[0], new List<int> { currentNumbers[1] });
           }

           if (numbers.ContainsKey(currentNumbers[1]))
           {
               numbers[currentNumbers[1]].Add(currentNumbers[0]);
           }
           else
           {
               numbers.Add(currentNumbers[1], new List<int> { currentNumbers[0] });
           }
       }

       isUsed[1] = true;

      DFS(1, numbers, isUsed);

      int count = isUsed.Count(x => x);
      Console.WriteLine(count - 1);

    }

    public static void DFS(int current, Dictionary<int, List<int>> numbers, bool[]  isUsed)
    {
        // 오잉 오잉
        if (!numbers.ContainsKey(current))
            return;
        foreach (int nextNumber in numbers[current])
        {
            if (!isUsed[nextNumber])
            {
                isUsed[nextNumber] = true;
                DFS(nextNumber, numbers, isUsed);
            }
        }
    }


}

 

우선, 네트워크 연결은 양방향이므로 채널(바이러스 전파 통로)을 양방향으로 기록해야 했다. 한 방향으로만 탐색한다면 실제로 연결되어 있음에도 전파가 되지 않는 상황이 생길 수 있기 때문이다. 이는 단순히 숫자 순서로만 전파가 이루어지지 않기 때문이다.

이후 DFS를 통해 1번 컴퓨터에서 시작해 바이러스가 퍼질 수 있는 모든 컴퓨터를 탐색했다. DFS는 연결된 모든 노드를 재귀적으로 방문하기 때문에 간접적인 전파도 놓치지 않는다.