[DFS/BFS] BOJ 2606 - 바이러스 / python

문제링크

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

문제

입출력

💡 사고의 흐름

• 컴퓨터가 연결된 구조 -> graph
• 1번 컴퓨터가 무조건 웜 바이러스에 걸림 -> 1번부터 탐색하면 됨.
• graph 는 n x n 크기 (1번부터 n번까지니까 1, n+1로 탐색!)
• 주어진 노드 수만큼 graph에 1로 마킹을 하고, check 리스트를 두어 탐색한다.
• 탐색한 만큼 cnt+=1를 해주어 감염된 컴퓨터(1번 제외) 수를 카운팅한다.

Code (DFS)

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[0 for _ in range(N+1)] for _ in range(N+1)] 
check = [0] *(N+1)
cnt = 0
def dfs(node):
  global cnt
  check[node]= True
  for i in range(1,N+1):
    if graph[node][i] == 1 and check[i]==False:
      cnt+=1
      dfs(i)
  return cnt
    
for i in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a][b]=1
  graph[b][a]=1

print(dfs(1))

Code (BFS)

import sys
from collections import deque
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph=[[0 for _ in range(n+1)] for _ in range(n+1)]
check=[False for _ in range(n+1)]

def bfs(x):
  cnt=0
  q = deque()
  check[x]=True
  q.append(x)
  while q:
    tmp =q.popleft()
    for i in range(1,n+1):
      if graph[tmp][i] ==1 and check[i]==False:
        q.append(i)
        check[i]=True
        cnt+=1
  return cnt
  
if __name__=='__main__':
  for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())
    graph[a][b]=1
    graph[b][a]=1
  print(bfs(1))

+) 수정 2/9