[백준] 2606 바이러스 (BFS)

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

2606번: 바이러스

 

 

""" 백준 2606 - 바이러스
1. 아이디어
- 값 1 && 방문 X -> BFS
- BFS 돌면서 갯수 구하기

2. 시간복잡도
O(V+E)

3. 자료구조
- 전체: computers[][]
- 값 확인: visited[][]

 

4. 로직 순서

1) computers 리스트의 인덱스 값을 통해 n 개의 컴퓨터가 각각 연결된 컴퓨터를 확인하도록 생성해준다.

2) 1-2가 연결되어 있다면 2-1도 연결되어 있는 것이므로, 두 방향에 대한 정보를 입력해준다.

3) BFS 는 deque 안에 리스트를 사용한다.

4) BFS 는 큐 자료구조 안에 모든 값이 없어질 때 까지 반복한다.

5) 가장 먼저 기입된 요소(여기서는 1번)를 pop 해주면서(꺼내주면서) visited 표시를 한다.

6) visited 표시 된 컴퓨터의 리스트가 갖고 있는 요소를 큐 구조에 append 해준다.

7) visited 표시가 되지 않은(큐 안에 삽입이 된 적 없는) i 값만을 사용해서 cnt를 증가시켜 준다.

 

 

 

5. 발생했던 문제들

1) 엔터값을 구분자로 두 정수를 입력 받는 방법을 몰랐었다. -> input(), input() 따로 입력받으면 됨

 

+ 기존에 풀었던 BFS 문제들(2178, 2667)과의 차이점은,

입력 값을 받아 새로운 리스트를 생성한다는 것, 

"""

 

---

from collections import deque

import sys

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

computers = [[] for i in range(n+1)]
visited = [False] * (n+1)
cnt = 0

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

def bfs(computers, v):
    global cnt
    q = deque([v])

    while q:
        pop = q.popleft()
        visited[pop] = True

        for i in computers[pop]:
            if visited[i] == False:
                visited[i] = True
                q.append(i)
                cnt += 1

    print(cnt)

bfs(computers, 1)