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

[ 문제 ]

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

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

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

 

[ 코드 ]

1. 내 코드

- DFS

int n = int.Parse(Console.ReadLine());
int m = int.Parse(Console.ReadLine());

List<int>[] list = new List<int>[n + 1];
bool[] check = new bool[n + 1];
int count = 0;

for (int i = 1; i <= n; i++)
{
    list[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]);

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

DFS(1, list, check);

for(int i = 2; i <= n; i++)
{
    if (check[i]) count++;
}

Console.Write(count);

void DFS(int node, List<int>[] list, bool[] check)
{
    check[node] = true;

    foreach(int i in list[node])
    {
        if (!check[i])
        {
            DFS(i, list, check);
        }
    }
}

 

2. 다른 사람 코드

- BFS

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

namespace BaekJoon_s_Note//5430
{
    class Node
    {
        int number;
        public bool founded;
        public List<Node> connectedNode = new List<Node>();

        public Node(int item)
        {
            this.number = item;
        }
        public void Connecting(Node node)
        {
            connectedNode.Add(node);
        }
    }
    class NetWork
    {
        List<Node> map = new List<Node>();
        Queue<Node> resevedNode = new Queue<Node>();
        Node temp;
        int cnt = 0;

        public void CreateNodes(int T_1)
        {
            for (int i = 1; i <= T_1; i++)
            {
                map.Add(new Node(i));
            }
        }
        public void nodeConnecting(int[] input)
        {
            map[input[0] - 1].Connecting(map[input[1] - 1]);
            map[input[1] - 1].Connecting(map[input[0] - 1]);
        }
        public void BFS()
        {
            resevedNode.Enqueue(map[0]);

            while (resevedNode.Count > 0)
            {
                temp = resevedNode.Dequeue();
                temp.founded=true;
                foreach (var item in temp.connectedNode)
                {
                    if (item.founded)
                    {
                        continue;
                    }
                    resevedNode.Enqueue(item);
                    item.founded = true;
                    cnt++;
                }
            }
        }
        public void Answer()
        {
            Console.WriteLine(cnt);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            NetWork netWork = new NetWork();

            int countOfComputer = int.Parse(Console.ReadLine());
            int abc = int.Parse(Console.ReadLine());

            int[] input;

            netWork.CreateNodes(countOfComputer);
            for (int i = 0; i < abc; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                netWork.nodeConnecting(input);
            }
            netWork.BFS();
            netWork.Answer();
        }
    }
}

 

[ 추가 ]

DFS : 깊이 우선 탐색(Depth-First Search)

BFS : 너비 우선 탐색(Breadth-First Search)

1. 탐색 순서:
   • DFS: 한 방향으로 최대한 깊이 들어가면서 탐색. 자식 노드를 탐색하기 전에 해당 분기의 모든 자식 노드를 방문. 이후에는 백트래킹을 통해 다른 분기로 이동
   • BFS: 한 레벨씩 너비를 우선으로 탐색. 현재 노드와 같은 레벨에 있는 모든 노드를 먼저 방문한 후에 다음 레벨의 노드를 방문
2. 데이터 구조:
   • DFS: 스택 또는 재귀 함수를 사용하여 구현
   • BFS: 큐를 사용하여 구현
3. 적합한 상황:
   • DFS: 그래프가 깊이가 얕고 해결책이 높은 곳에 있을 때 적합. 또한, 해결책이나 경로가 하나라도 발견되면 탐색을 종료할 수 있는 경우
   • BFS: 그래프가 넓고 레벨 단위로 탐색해야 할 때 적합. 최단 경로를 찾거나 최단 거리를 구하는 문제 등
4. 시간 복잡도 (V는 정점의 수, E는 간선의 수):
   • DFS: O(V + E) 
   • BFS: O(V + E)

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

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

2606번: 바이러스