[파이썬] 2606. 바이러스

문제

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

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

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

입력

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

출력

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

예제 입력 1 

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력 1 

4

 

 

👧 나의 풀이

 

import sys
from collections import defaultdict, deque

input=sys.stdin.readline
N=int(input())  # 컴퓨터 개수
dic=defaultdict(list)
visited=[0]*(N+1)

# 연결 정보
for i in range(int(input())) :
    x, y=map(int, input().split())
    dic[x].append(y)
    dic[y].append(x)

def bfs() :
    cnt=0
    que=deque()
    que.append((1))
    while que :
        com=que.popleft()
        visited[com]=1
        for i in dic[com] :
            if not visited[i] and i not in que :
                que.append((i))
                cnt+=1
    print(cnt)

bfs()

 

bfs로 구현

딕셔너리 dic에 컴퓨터 간 연결 정보를 담았다.

com에 연결 된 컴퓨터 중 방문한 적 없고 que에 없으면 append한다.

append할 때마다 1씩 늘렸다.

 

 

👱‍♀️ 다른 사람 풀이

 

import sys

n=int(sys.stdin.readline())		# 컴퓨터 수
m=int(sys.stdin.readline())		# 컴퓨터 쌍의 수

graph=[[0]*n for i in range(n+1)]
visit=[False]*(n+1)
visit[0]=True

for i in range(m) :
    a, b=map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph, i) :
    visit[i]=True
    for i in graph[i] :
        if visit[i] == False :
            dfs(graph, i)

dfs(graph, 1)
print(visit.count(True)-2)

 

재귀를 이용한 dfs

방문한 컴퓨터의 수를 세서 출력한다.

 

graph

graph=[[0]*n for i in range(n+1)]에서 0을 n개 만들고 또 그 뒤에 컴퓨터 쌍을 append한 결과다.

dfs의 for i in graph[i]에서 필요없는 반복을 하게된다.

graph=[[] for i in range(n+1)]로 했어야함..

graph 수정한 후

출력할 때 -2를 해주는 이유는 0번, 1번 컴퓨터 제외할려고.

0번으로 갈 일이 없는데 visit[0]=True를 왜 하지? 안 하고 -1해도 됨.

 

 

import sys

def dfs(graph, visited, v) :
    # 현재 노드를 방문처리
    visited[v]=True

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    i=graph.get(v)
    for j in range(len(i)) :
        if not visited[i[j]] :
            dfs(graph, visited, i[j])

    return visited

n=int(sys.stdin.readline()) # n= 컴퓨터 수
con=int(sys.stdin.readline())   # con=연결되어 있는 컴퓨터 쌍의 수
graph={}    # 각 노드가 연결된 정보
for _ in range(con) :
    a, b=map(int, sys.stdin.readline().split())

    if a not in graph :
        graph[a]=[b]
    else :
        graph[a].append(b)
    if b not in graph :
        graph[b]=[a]
    else :
        graph[b].append(a)

visited=[False]*(n+1)   # 각 노드가 방문한 정보
visited=dfs(graph, visited, 1)
cnt=0
for i in range(2, n+1) :
    if visited[i] :
        cnt+=1
print(cnt)

 

재귀로 dfs로 구현

딕셔너리 graph에 컴퓨터 입력할 때 defaultdict를 쓰면 편하게 조건문 없이 append할 수 있다.

get은 딕셔너리 key 값을 반환한다.

visited를 return할 필요가 없다. 전역변수니까

 

 

문제 출처 💁‍♀️ 백준