2606 바이러스 파이썬

문제

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

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

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

입력

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

출력

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

 

 

 

핵심을 보면, 이문제는 연결되어 있는 노드의 개수-1 을 구하는 것과 같다.

입력 및 변수로는

1.컴퓨터 수 : C

2.연결된 쌍 : N

3.노드 배열:arr, visited

4.방문할 노드 배열: need_visit

5.그래프 용 배열 : com

 

 

그래프를 입력을 받아서 bfs로 방문한 노드를 visited에 넣고, 1이 포함되어 있으니 len(visited)-1을 출력해주면 되는 문제였다.

 

 

 

부족했던 점 :

1. 일단 그래프형식으로 어떻게 입력 받을지가 가장 문제였다. 대개 딕셔너리를 쓰므로, 딕셔너리로 입력을 받으려고 했는데, 자꾸 value가 덮어쓰기 됐다. 하나의 key값에 여러 value를 입력으로 받는 방법을 몰랐다.

그래서 차선책으로 2중배열인데 비어있고, 컴퓨터 개수+1로 만들었다.

 

2.반례를 통해서 찾아낸 건데, 배열로 그냥 첫번째 두번째를 단순히 key,value로 넣기만 하면

2 1 이라는 데이터가 있을 때 2라는 key를 찾으면 정상적으로 작동하지만, 1이라는 key에는 2가 없게 된다.

즉 반대로도 배열에 데이터를 업데이트 해줘야 한다는 얘기다.

 

이 두가지를 빼면 전형적인 bfs문제였다.

 

 

 

 

 

#컴퓨터 수 :C
C=int(input())
#연결된 쌍
N=int(input())
com=[ [] for _ in range(C+1) ]


for i in range(N):
    key,value=map(int,input().split())
    com[key].append(value)
    com[value].append(key)     # 역으로도 데이터 입력해주기.

def bfs(start):
    need_visit=[start]
    visited=[]

    while need_visit:
        node=need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            for i in com[node]:
                need_visit.append(i)

    return visited
arr=bfs(1)
print(len(arr)-1)  #1을 뺀값을 출력