[백준 2606번] 바이러스

 

from collections import deque

vertex_count = int(input())
edge_count = int(input())

graph = [[] for _ in range(vertex_count + 1)]

for _ in range(edge_count):
    x, y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [False] * (vertex_count+1)

count = 0

def dfs(graph, v, visited):

    global count

    visited[v] = True
    
    count += 1
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

def bfs(graph,v,visited):
    
    global count

    visited[v] = True

    queue = deque([v])

    while queue:
        node = queue.popleft()
        count += 1
        
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    

# dfs(graph,1,visited)
bfs(graph,1,visited)
print(count-1)

이번 문제는 네트워크(간선)로 연결되어 있는 컴퓨터(노드, 정점)이 존재할 때, 하나의 컴퓨터에서 바이러스가 시작되어 전파되는 컴퓨터의 수를 찾는 문제이다. 

 

이 문제같은 경우에는 하나의 정점으로부터 모든 정점을 방문하면서 카운팅을 해야 하기 때문에 DFS나 BFS 알고리즘 중 뭐든 사용해도 상관없다.( https://woohyun-king.tistory.com/30 참고 )

[BFS] BFS 알고리즘의 개념 및 동작과정 / DFS와 BFS 선정 기준

 

따라서 본인은 DFS와 BFS를 연습하기 위하여 두 알고리즘을 모두 사용하여 문제를 풀이해보았다.

 

한 정점으로부터 다른 정점들로 이동해가며 탐색하는 탐색의 2가지 알고리즘인 DFS와 BFS의 개념과 동작방식을 이해하고, 문제 조건에 따라 구현해보는 연습을 해볼 수 있었던 좋은 문제였다 :)