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

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

2606번: 바이러스

 

from collections import deque

n = int(input())
m = int(input())
graph = [[0]*(n+1) for i in range(n+1)]
visit = [0]*(n+1)
for i in range(m):
    line = list(map(int,input().split()))
    graph[line[1]][line[0]] =1
    graph[line[0]][line[1]] =1

def bfs(start,graph,visit):
    visit[start] = 1
    com=deque()
    com.append(start)
    cnt =0
    while com:
        v=com.popleft()

        for i in range(len(graph[v])):
            if visit[i] != 1 and graph[v][i] ==1 :
                com.append(i)
                visit[i] = 1
                cnt += 1
    return cnt

print(bfs(1,graph,visit))

bfs 로 풀었는데 dfs 로 풀어도 될거 같은 느낌...?

 

https://jiwon-coding.tistory.com/93

[백준] 2606번 바이러스 / 파이썬(python)

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)

그래프 만드는 방식도 고려해도 될거 같다.