[백준] 2606번 바이러스 / 파이썬 / python / BFS,DFS

📌 문제

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

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

 

😈 입력

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

 

💬 출력 

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

 

---

👩‍💻 code

import sys
input=sys.stdin.readline

n=int(input())
pair=int(input())

array=[[0]*(n+1) for _ in range(n+1) ]


for _ in range(pair):
    a,b=map(int,input().split())
    array[a][b],array[b][a]=1,1

visited=[]




# dfs 방식
def dfs(start,array,visited):
    visited.append(start)
    for i in range(n+1):
        if array[start][i] and i not in visited:
            visited=dfs(i,array,visited)
    return visited
    
    
    
    
    
# bfs 방식
from collections import deque

def bfs(start,array):
    visited=[]
    queue=deque([start])
    visited.append(start)
    while queue:
        start=queue.popleft()
        for i in range(n+1):
            if array[start][i] and i not in visited:
                queue.append(i)
                visited.append(i)
    return len(visited)-1




print(len(dfs(1,array,visited))-1)
print(bfs(1,array))

---

💕 해설

2차원 배열을 사용하였고 bfs, dfs모두 구현해보았다.
기본적인 bfs,dfs문제였다.
2차원 배열에서 입력값으로 주어진 연결 쌍들에 해당하는 것들은 모두 1로, 나머지는 0으로 둠.

+ 다른분 풀이에서 2차원 배열이 아니라 딕셔너리를 사용해서 넣은 것도 있었는데
value를 set()으로 두어 자동으로 중복을 배제해주었다. 좋은 아이디어인듯 !