백준-2606-바이러스

구현 코드

import sys
from collections import deque

def bfs(graph, start, visited):
    #bfs구현을 위한 큐 선언
    queue = deque([start]) #start부터 큐를 선언하면서 넣고 시작

    #현재 노드 방문 처리
    visited[start] = 1

    #큐에 값이 없을 때까지 반복
    while queue:
        temp = queue.popleft()

        for i in graph[temp]:
            if visited[i] == 0: # 해당 노드와 인접 노드가 방문한 적이 없을때
                queue.append(i) # 큐에 삽입
                visited[i] = 1 # 방문처리

n = int(input()) # PC 수
m = int(input()) # PC가 연결된 쌍 수

graph = [[] for i in range(n+1)] # 컴퓨터 개수만큼 그래프 초기화 , 0번부터시작하는 리스트 고려
visited = [0] * (n+1)

for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
	
    #연결리스트로 그래프를 생성
    graph[a].append(b)
    graph[b].append(a)

print(graph)

bfs(graph,1,visited)

# visited에서 1인 개수를 출력
print(visited.count(1) - 1) # 자기 자신 제외

• 본 문제는 그래프 형식으로 생각해서 풀이할 수 있는 문제이다.
• 그래서 그래프 탐색 문제를 빠르게 해결할 수 있는 BFS를 이용하여 풀이했다.
• BFS는 큐 자료구조를 활용하여 그래프를 넓이 우선으로 탐색하는 알고리즘이다.
• 1번 컴퓨터를 통해서 웜 바이러스가 걸리게 되는 컴퓨터 수는 연결리스트가 연결되어 있는 컴퓨터의 수를 세면 해결된다.
• BFS를 통해서 노드를 순회하며 방문한 노드를 기록하고, 방문한 노드의 개수를 세고 1번 노드의 개수인 하나를 빼주게되면 1번 컴퓨터에의해서 감염된 컴퓨터의 개수가 나오게 된다.

 

문제링크