[Python] 2606번 바이러스

문제

https://www.acmicpc.net/problem/2606

풀이과정

• 문제 설명 한 컴퓨터가 바이러스에 걸리면 연결되어 있는 컴퓨터는 바이러스에 걸린다. → 구해야 하는 것과 같다.
  
• 풀이 해당 index와 연관되어 있는 것을 넣어준다. 예제 입력 시

  7
  6
  1 2
  2 3
  1 5
  5 2
  5 6
  4 7

  [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]] 1부터 시작해서 해당 index를 방문처리 해준다 → index와 연관되어 있는 곳을 탐색하는데 방문한 곳이라면 생략한다. → dfs를 다시 실행해서 방문처리 해준다.
  

• DFS

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
# 서로 연관이 있으니 index는 value들과 연결되어 있다!
visited = [False for _ in range(n+1)]
cnt = 0

def dfs(x):
    global cnt
    visited[x] = True  # 방문처리
    cnt += 1
    for i in g[x]:
        if visited[i]:  # 방문한 곳이라면
            continue  # 생략
        dfs(i)

dfs(1)
print(cnt-1) # 자기자신 방문은 제외한다.

• BFS

from collections import deque
def bfs(x):
    q = deque([x])
    cnt = 0
    visited[x] = True
    while q:
        node = q.popleft()
        for next_node in g[node]:
            if not visited[next_node]:
                visited[next_node] = True
                q.append(next_node)
                cnt += 1
    return cnt