[C#]백준 2606 바이러스 - Hide

반응형

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

문제 요약

1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수 출력하기

 

 

 

틀린 풀이

var R=()=>Console.ReadLine().Split().Select(int.Parse).ToList();var t=R();int i=R()[0];List<int> l=new(){1};
for(;i-->0;){t=R();if(l.Contains(t[0])||l.Contains(t[1]))l.AddRange(t);}
Console.Write(l.Distinct().Count()-1);

순서쌍 둘 중에 하나라도 리스트에 있으면 리스트에 t를 전부 다 추가

이후 중복 제거 후에 1을 뺀다.

 

이 코드의 문제 : 컴퓨터 쌍이 순서대로 주어지지 않기 때문에 반복문 몇번으로는 서로 연결되어 있는지 알 수 없다.

예를 들어 예제의 컴퓨터 쌍이 주어질 때

1 2

5 6

4 7

2 3

1 5

5 2

이런 순서라면 5-6과 4-7은 리스트에 추가되지 못하므로 답이 3으로 나온다.

 

 

 

맞은 풀이(DFS사용)

var R=()=>Console.ReadLine().Split().Select(int.Parse).ToArray();int N=R()[0],M=R()[0],c=0;
var g=new List<int>[N+1];
for(int i=1;i<=N;)g[i++]=new();
for(int i=0;i<M;i++){var t=R();g[t[0]].Add(t[1]);g[t[1]].Add(t[0]);}
var v=new bool[N+1];DFS(1);Console.Write(c-1);
void DFS(int i){v[i]=true;c++;foreach(var n in g[i])if(!v[n])DFS(n);}

DFS 할 때랑 거의 똑같은 방식. 개수를 구하는 문제라서 g[i].Sort()할 필요는 없다.

---

오랜만