[Algorithm] 백준 2606 : 바이러스

문제
https://www.acmicpc.net/problem/2606
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/2606.%E2%80%85%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4/%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4.py

dfs와 bfs를 이용하는 간단한 문제였다. 이전에 푼 프로그래머스 네트워크 문제와 매우 유사했는데, 약간 다른 점이 있다면 bfs, dfs의 start 파라미터로 들어가는 인자 값이 1번 컴퓨터로 고정되어 있다는 점이었다.

1번 컴퓨터에 의해 바이러스에 걸린 컴퓨터의 수를 구하고 싶었기 때문에 1번 컴퓨터를 제외한 감염된 컴퓨터의 수를 출력하면 되는 문제였다.

이 문제 또한 dfs, bfs 메소드를 생성하여 각각의 방식으로 풀어보았다.

< 풀이 코드 >

import sys
from collections import deque

def dfs(start, visited, graph, result): # 재귀
  visited[start] = True
  result.append(start)
  for i in range(len(visited)):
    if (not visited[i]) and (graph[start][i]):
      dfs(i, visited, graph, result)

def bfs(start, visited, graph,result): #큐
  queue = deque([start])
  visited[start] = True

  while queue:
    v = queue.popleft()
    result.append(v)

    for i in range(len(visited)):
      if(not visited[i]) and (graph[v][i]):
        queue.append(i)
        visited[i] = True


computers = int(sys.stdin.readline())
connections = int(sys.stdin.readline())

graph = [[False]*computers for i in range(computers)]
visited = [False]*computers

for i in range(connections):
  a, b = map(int,sys.stdin.readline().split())
  graph[a-1][b-1] = True
  graph[b-1][a-1] = True

result = []

dfs(0,visited, graph, result)
print(len(result) - 1)