[알고리즘 문제풀이] 바이러스

문제 제목 : 바이러스

문제 난이도 : 하

문제 유형 : BFS, DFS

https://www.acmicpc.net/problem/2606
시간 제한 : 1초
메모리 제한 : 128MB

문제풀이 아이디어

• 기본적인 DFS, BFS로 풀면 된다.
• 1번 노드에서 감염된 컴퓨터의 개수이므로 전체 카운트에서 -1을 해줘야 한다.

< 소스코드 >

from collections import deque
n = int(input())
m = int(input())
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
    
# dfs 풀이
def dfs(now_pos):
    global count
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)
    count = visited.count(True) - 1
  
# bfs 풀이
def bfs(now_pos):
    global count
    q = deque([1])
    while q:
        now_pos = q.popleft()
        if not(visited[now_pos]):
            visited[now_pos] = True
            for next_pos in adj[now_pos]:
                if not visited[next_pos]:
                    q.append(next_pos)
    count = visited.count(True) - 1

bfs(1)
print(count)

dfs(1)
print(count)