[BOJ] 2602. 바이러스

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

2606번: 바이러스

 

1. 해결방법

"""
1. 아이디어
- 그래프 배열에서 a vertex에 b vertex를 append 시킨다.
- BFS 돌면서 다녀간 vertex는 방문기록 배열로 처리한다.
- BFS를 돌면서 감염된 컴퓨터의 수를 구한다.

2. 시간복잡도
- O(n^2) : 100^2 X M

3. 자료구조
- 2차원 배열 : int[][], bool[][]
- BFS : Queue
"""

 

 

2. 정답코드

 

입력 예제(1)

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

출력 예제(1)

4

 

 

코드

import sys
from collections import deque


# input or data
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n + 1)]
chk = [False] * (n + 1)
cnt = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# bfs
def bfs(start):
    global cnt
    q = deque()
    q.append(start)
    chk[start] = True
    while q:
        now = q.popleft()
        for vertex in graph[now]:
            if chk[vertex] == False:
                cnt += 1
                chk[vertex] = True
                q.append(vertex)
    return cnt

bfs(1)
print(cnt)