[baekjoon] 백준 2606번 : 바이러스 (by python 파이썬) bfs dfs 두가지 풀이

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

2606번: 바이러스

 

정답 code

-dfs 활용

#dfs이용
def dfs(com, x):
    global cnt
    visited[x] = True
    
    for i in com[x]:
        if visited[i] == False:
            dfs(com,i)
            cnt += 1    
    return True
    


n = int(input())
c = int(input())
cnt = 0
com = [[] for _ in range(n+1)]

for _ in range(c):
    x, y  = map(int,input().split())
    com[x].append(y)
    com[y].append(x)

visited = [False] * (n+1)

dfs(com,1)
print(cnt)

 

-dfs 활용

# bfs 이용
from collections import deque

def bfs(com, x):
    cnt = 0
    queue = deque()
    queue.append(x)
    while queue:
        x = queue.popleft()
        visted[x] = True

        for i in com[x]:
            if visted[i] == False:
                queue.append(i)
                visted[i] = True
                cnt += 1
    print(cnt) 

n = int(input())
c = int(input())

com = [[] for _ in range(n+1)]


for _ in range(c):
    x, y  = map(int,input().split())
    com[x].append(y)
    com[y].append(x)

visted = [False]*(n+1)
bfs(com , 1)

 

 

solution

이번 문제는 bfs나 dfs를 이용하여 간편하게 풀 수 있다.

여기서 신경써야 될점은 컴퓨터 1로 부터 탐색을 해나갈때 카운트(cnt)를 해주어 바이러스에 걸리게 되는 컴퓨터를 세어야 한다.