[Python] 백준 #2606 - 바이러스

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

2606번: 바이러스

 

내 코드 (BFS)

import sys
from collections import deque

def bfs(graph,visited,start):
    queue = deque([start])
    visited[start] = True
    cnt=0
    while queue:
        v = queue.popleft()
        cnt+=1
        for i in graph[v]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True
    return cnt

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

graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

print(bfs(graph,visited,1)-1)

1번 컴퓨터를 통해서 감염되는 컴퓨터의 수를 구하는 문제이다. bfs로 풀었다. 

1번 컴퓨터는 제외해야하므로 -1을 해준다.

 

 

 

다른사람 코드 (DFS)

n = int(input())
m = int(input())
graph = [[]*n for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
cnt = 0
visited = [0]*(n+1)
def dfs(start):
    global cnt
    visited[start] = 1
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt +=1
 
dfs(1)
print(cnt)

dfs로 푼 방법을 들고와봤다. cnt를 전역변수로 만들어주고 답을 구해주었다. 

 

코드 출처 - https://jiwon-coding.tistory.com/93