[탐색/BFS] 백준 2606 바이러스 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2606번: 바이러스

 

 

 

2. 문제 풀이

 1번 컴퓨터와 연결되어 있는 컴퓨터의 수를 구하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 그래프 탐색 문제로, DFS와 BFS 모두 가능합니다. 저는 BFS를 사용했습니다.

 

 

 

3. 코드

from collections import deque
import sys
input = sys.stdin.readline

# BFS 탐색 (탐색할 그래프, 노드 수, 시작 지점)
def bfs(graph, n, start):
    queue = deque([start]) #인접 노드를 저장할 Queue

    visited = [False]*(n+1) #방문 여부를 확인할 리스트
    visited[start] = True #시작 노드 방문
    res = 0 #감염된 컴퓨터 개수

    #모든 노드를 탐색할 때까지 반복
    while queue:
        #방문 노드
        node = queue.popleft()
        res += 1

        #방문한 노드의 주변 노드를 큐에 삽입
        for i in graph[node]:
            #방문하지 않는 주변 노드일 경우
            if not visited[i]:
                queue.append(i) #큐에 추가
                visited[i] = True #방문
    return res

nodeNum = int(input())
edgeNum = int(input())
graph = [ [i] for i in range(nodeNum+1) ]

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

print(bfs(graph, nodeNum, 1)-1) #1번 노드 제외

 1번부터 n번 노드까지의 인접노드가 주어지는 게 아니라, 각각의 쌍으로 주어집니다.

 따라서 graph[a].append(b) graph[b].append(a)와 같이, 직접 추가해줘야 합니다.