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

📌문제 출처

솔브닷 3+ 클래스 단계
https://www.acmicpc.net/problem/2606

2606번: 바이러스

❓ 문제

❗ 풀이

• bfs 활용 풀이

📗 풀이 코드

import sys
from collections import deque, defaultdict
input = sys.stdin.readline
def bfs(i):
    stack = deque([i])
    while stack:
        for j in dic[stack.popleft()]:
            if not visited[j] : # 방문한 적이 없다면
                visited[j]=1 # 방문표시
                stack.append(j)
    return sum(visited.values())

n = int(input())
dic = defaultdict(list)
for _ in range(int(input())):
    a,b = map(int,input().split())
    dic[a].append(b)
    dic[b].append(a)
    
visited = {i:0 for i in range(1,n+1)}
visited[1] = 1
print(bfs(1)-1)

📗 코드 해설

• dic에는 한 노드에서 갈 수 있는 다른 노드를 넣어두고 visited에는 방문 이력을 넣어둔다.
  이때 visited[1]=1로 해두고 마지막에 노드 개수에서 1을 빼주어야 1을 새로 방문하지도 않고, 1번 컴퓨터의 개수도 뺄 수 있다.
• bfs를 돌며 해당 노드에서 방문할 수 있는 모든 노드를 stack에 넣어주고 동시에 방문 이력도 1로 변경해준다.
• bfs가 종료되면 가능한 모든 노드를 방문한 것이므로 방문 가능한 노드의 개수를 출력한다.