[백준] 2606 파이썬 - 바이러스

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

2606번: 바이러스

1번 컴퓨터를 통해 웜바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 알고리즘을 짜면 된다. 

위의 그림을 보면 1과 연결되어있는 2, 5, 3, 6 이렇게 4대가 바이러스에 걸리는 걸 알 수 있다. 

이 문제 또한 그래프이다. 

 

인접 행렬로 푸는 방법과 인접리스트로 푸는 방법을 각각 bfs와 dfs로 구현했다. 

 

1. 인접행렬

#2606
#1번 컴퓨터가 웜바이러스에 걸렸을 때 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 

from collections import deque

C=int(input())#컴퓨터 수
connect=int(input())#연결되어있는 컴퓨터 쌍의 수

network=[[0]*(C+1) for _ in range(C+1)]

#방문 기록
visited_dfs=[0]*(C+1)
visited_bfs=[0]*(C+1)

#그래프 채우기 : 인접행렬
for _ in range(connect):
    a,b=map(int,input().split())
    network[a][b]=1
    network[b][a]=1

#-------------------함수------------------

def dfs(v):
    visited_dfs[v]=1
    for i in range(1,C+1):
        if(visited_dfs[i]==0 and network[v][i]==1):
            dfs(i)#더 깊이 탐색

def bfs(v):
    queue=deque([v])
    visited_bfs[v]=1

    while queue:
        v=queue.popleft()

        for i in range(1,C+1):
            if(visited_bfs[i]==0 and network[v][i]==1):
                queue.append(i)#추가
                visited_bfs[i]=1#방문 처리


dfs(1)
print(sum(visited_dfs)-1)

 

2. 인접리스트

#2606 인접 리스트로 풀기

from collections import deque

N=int(input())
M=int(input())


graph = [[] for _ in range(N+1)]	

#기록
visited=[0]*(N+1)

#인접리스트 만들기
for i in range(M):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

#깊이탐색
def dfs(v):
    visited[v]=1
    for i in graph[v]:
        if visited[i]==0:
            dfs(i)
#넓이 탐색
def bfs(v):
    queue=deque([v])
    visited[v]=1

    while queue:
        v=queue.popleft()

        for i in graph[v]:
            if visited[i]==0:
                queue.append(i)
                visited[i]=1


dfs(1)
print(sum(visited)-1)

어려운 문제는 아니라서 그냥 정점과 간선이 입력되면 그래프를 만들고 탐색만 하면 되는 문제였다.