[Python] BOJ/백준 2606번 바이러스

[문제]

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

2606번: 바이러스

 

[풀이]

2021.08.18 - [BOJ] - [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙

[Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙

2021.08.25 - [BOJ] - [Python] BOJ/백준 11724번 연결 요소의 개수

[Python] BOJ/백준 11724번 연결 요소의 개수

 

위의 두 문제와 같이 BFS 탐색으로 풀이했다.

 

인덱스는 0부터 시작하지만 문제에서 나오는 컴퓨터는 1부터 시작하기 때문에 리스트의 인덱스를 0이 아닌 1부터 시작해야 한다.

따라서 (노드 수 + 1) 만큼 visited 리스트를 False로 초기화해놓는다.

 

bfs 함수에 처음 들어가게 되면 처음 1번 컴퓨터를 방문한 것이기 때문에 visited[1] 를 True로 변경해놓는다.

queue에 값이 있을 동안 while문을 반복하며 queue의 맨 앞의 값을 꺼내 해당 값이 연결되어 있는 노드들을 살핀다.

차례인 노드를 인덱스로 하여 visited[노드] 값이 False이면(이전에 방문 한 적 없는 노드이면) 새로 연결해야 되는 노드이기 때문에 queue에 해당 노드를 추가하고, visited[노드] 값을 True로 변경한다. 

 

[코드]

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = True

    count = 0
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if not visited[i]:
                count += 1
                queue.append(i)
                visited[i] = True
    return count


if __name__ == '__main__':
    computer = int(input())
    connect = int(input())
    graph = [[] for i in range(computer + 1)]

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

    visited = [False] * (computer + 1)
    print(bfs(1))