[BOJ] 백준 2606번 - 바이러스 (Python)

문제

문제 바로가기

해결

from collections import deque

n = int(input())
e = int(input())
g = list()
q = deque()
infected = list()
cnt = 0

for _ in range(n+1):
  line = []
  for _ in range(n+1):
    line.append(0)
  g.append(line)

for _ in range(e):
  s, d = map(int, input().split())
  g[s][d] = 1
  g[d][s] = 1

q.append(1)
infected.append(1)
while q:
  point = q.popleft()
  for i in range(n+1):
    if g[point][i] == 0:
      continue
    if i in infected:
      continue
    else:
      q.append(i)
      infected.append(i)
      
print(len(infected) - 1)

고찰

Directed Graph와 Undirected Graph를 잘 생각하자.. 그리고 너비 우선 탐색일 경우에는 뒤돌아가지 않는 걸 잘 생각해두자.