알고리즘/백준

백준-2606-바이러스

hong2943 2024. 5. 3. 13:10

구현 코드

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번 컴퓨터에의해서 감염된 컴퓨터의 개수가 나오게 된다.

 

문제링크

'알고리즘 > 백준' 카테고리의 다른 글

백준-9095-1, 2, 3 더하기  (0) 2024.06.17
백준-2775-부녀회장이 될테야  (0) 2024.06.03
백준-1914-하노이 탑  (0) 2024.04.30
백준-17413-단어뒤집기  (0) 2024.04.29
백준-1966-프린터 큐  (0) 2024.04.29