바이러스(백준 2606번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?✓

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상✓

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

DFS, BFS 알고리즘을 코드로 구현하는 방법을 잘 몰라서, 솔루션을 찾아보았다. 이제 혼자서 풀 수 있을 것 같다.

문제

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

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

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

나의 풀이(DFS, BFS 알고리즘 참고)

import sys
from collections import defaultdict

def DFS(graph,i,visited):
    global count
    visited[i]=True
    count+=1
    for node in graph[i]:
        if not visited[node]:
            DFS(graph,node,visited)

N=int(input())
T=int(input())
graph=defaultdict(list)
visited=[False]*101
count=0

for _ in range(T):
    n1,n2=map(int,sys.stdin.readline().strip().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
DFS(graph,1,visited)
print(count-1)

• DFS를 사용해서 구현해보았다. 다음 문제는 BFS를 사용해서 구현해보려고 한다.
• 계속 틀렸다는 문구가 나오기도 했는데, n1,n2=map(int,sys.stdin.readline().strip().split()) 이 코드에서 int로 바꿔주는 작업을 하지 않았다. defaultdict()를 사용하면, error가 발생하지 않기 때문에 주의해야 할 것 같다.