실버3 바이러스(2606)

2606번: 바이러스

바이러스 문제는 DFS와 BFS를 활용해서 풀 수 있는 간단한 문제입니다. 알고리즘2 수강하면서 풀다보니 CC(Connected Component)배우면서 유형이 비슷하다고 생각했습니다.

# 바이러스
# https://www.acmicpc.net/problem/2606 

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, visited, node):
  queue = deque()
  queue.append(node)  
  visited[node] = True
  while queue:
    start = queue.popleft()
    for connectedNode in graph[start]:
      if not visited[connectedNode]:
        queue.append(connectedNode)
        visited[connectedNode] = True
  return visited

def dfs(graph, visited, node):
  visited[node] = True
  for connectedNode in graph[node]:
    if not visited[connectedNode]:
      dfs(graph, visited, connectedNode)
  return visited

v, e = int(input()), int(input())
connectedList = [[] for _ in range(v+1)]
visited = [False] * (v+1)

for i in range(e):
  x,y = map(int, input().split())
  connectedList[x].append(y)
  connectedList[y].append(x)

print(bfs(connectedList, visited, 1).count(True)-1)

위와 같이 풀이를 했습니다. DFS와 BFS에 대해서 오랜만에 하다보니 다시 공부해야 할것 같아서 두가지 방법을 모두 구현했습니다.

인접 리스트를 활용해서 DFS와 BFS를 했고, 반환 값을 visited로 반환하여 True를 count하여 계산했습니다.