백준 파이썬 2606 바이러스

백준 링크:https://www.acmicpc.net/problem/2606

2606번: 바이러스

dfs로 풀어도 되고 bfs로 풀어도 되는 문제이다.

 

1로 시작하는 트리가 몇개인지 파악하는 문제

 

dfs의 경우

n=int(input())
nums=int(input())

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

for i in range(nums):
    a,b = map(int,input().split())
    matrix[a][b] = 1
    matrix[b][a] = 1

def dfs(start,visited):
    visited += [start]
    for i in range(n+1):
        if matrix[start][i] == 1 and i not in visited:
            dfs(i,visited)
    return visited

print(len(dfs(1,[]))-1)

 

bfs의 경우

from collections import deque

n=int(input())
nums=int(input())

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

for i in range(nums):
    a,b = map(int,input().split())
    matrix[a][b] = 1
    matrix[b][a] = 1

queue = deque([])
queue.append(1)

visited=[0]*(n+1)

while queue:
    x = queue.popleft()

    visited[x] = 1

    for i in range(1,n+1):
        if matrix[x][i] == 1 and visited[i] == 0:
            queue.append(i)

print(visited.count(1)-1)