#146 백준 파이썬 [2606] 바이러스 - BFS

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

 

#Solution

문제의 카테고리가 플로이드 와샬 알고리즘으로 되어있어, 이 방법으로 계속 풀다가 시간 복잡도, 구현 방법 등등에 있어서 BFS(너비 우선 탐색) 알고리즘이 훨씬 더 효율적이므로 이를 통해 해결하였다. 결국 1과 연결된 것만 구하면 되니까. + 양방향 그래프라서 네트워크 정보를 한 번 뒤집어서 2차원 배열에 넣어줬다. 

computer = int(input())
network = int(input())
virus_map = [[0 for _ in range(computer + 1)] for _ in range(computer + 1)]

#2차원 배열 안에 넣어주기
for _ in range(network):
    x, y = map(int, input().split())
    virus_map[x][y] = 1
    virus_map[y][x] = 1


#1과 연결된 모든 노드 뽑기
def bfs(virus_map, start):
    queue = [start]
    visited = []
    
    while queue:
        temp = queue.pop(0)
        visited.append(temp)
        
        for i in range(len(virus_map)):
            if virus_map[temp][i] and i not in visited and i not in queue:
                queue.append(i)
                
    return len(visited) - 1


#1을 제외한 감염된 노드 수 출력
print(bfs(virus_map, 1))