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

백준 2606번 링크)

---

---

< dfs 사용 (재귀적)>

import sys
input=sys.stdin.readline

n,pair=int(input()),int(input())
matrix=[[0]*(n+1) for _ in range(n+1)]

for i in range(pair):
    adj=list(map(int,input().split()))
    matrix[adj[0]][adj[1]]=1
    matrix[adj[1]][adj[0]]=1

def dfs(start,row,visited):
    visited+=[start]
    for search in range(len(row[start])):
        if row[start][search] and search not in visited:
            visited=dfs(search,row,visited)
    return visited

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

< bfs 사용 (collections.deque) >

collections.deque 사용법

import sys
import collections

input=sys.stdin.readline
deq=collections.deque

n,pair=int(input()),int(input())
matrix=[[0]*(n+1) for _ in range(n+1)]

for i in range(pair):
    adj=list(map(int,input().split()))
    matrix[adj[0]][adj[1]]=1
    matrix[adj[1]][adj[0]]=1

def bfs(start,row,visited):
    queue=deq([start])
    visited=deq([start])
    while queue:
        start=queue.popleft()
        for search in range(len(row[start])):
            if row[start][search] and search not in visited:
                visited.append(search)
                queue.append(search)
    return visited

print(len(bfs(1,matrix,[]))-1)