반응형
[ 문제 ]
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 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)
- 탐색 순서:
- DFS: 한 방향으로 최대한 깊이 들어가면서 탐색. 자식 노드를 탐색하기 전에 해당 분기의 모든 자식 노드를 방문. 이후에는 백트래킹을 통해 다른 분기로 이동
- BFS: 한 레벨씩 너비를 우선으로 탐색. 현재 노드와 같은 레벨에 있는 모든 노드를 먼저 방문한 후에 다음 레벨의 노드를 방문
- 데이터 구조:
- DFS: 스택 또는 재귀 함수를 사용하여 구현
- BFS: 큐를 사용하여 구현
- 적합한 상황:
- DFS: 그래프가 깊이가 얕고 해결책이 높은 곳에 있을 때 적합. 또한, 해결책이나 경로가 하나라도 발견되면 탐색을 종료할 수 있는 경우
- BFS: 그래프가 넓고 레벨 단위로 탐색해야 할 때 적합. 최단 경로를 찾거나 최단 거리를 구하는 문제 등
- 시간 복잡도 (V는 정점의 수, E는 간선의 수):
- DFS: O(V + E)
- BFS: O(V + E)
[ 실행화면 ]
문제링크: https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍
www.acmicpc.net
반응형
'Language > C#' 카테고리의 다른 글
[C#] 백준 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (오름차순) (0) | 2024.04.10 |
---|---|
[C#] 백준 1032번 명령 프롬프트 (0) | 2024.04.09 |
[C#] 백준 1065번 한수 (1) | 2024.04.07 |
[C#] 백준 1654번 랜선 자르기 (0) | 2024.04.07 |
[C#] 백준 1388번 바닥 장식 (그래프- 깊이 우선 탐색(DFS)) (0) | 2024.04.06 |