PS/Python
[Python] 백준 #2606 바이러스 - bfs
yoo.o
2020. 8. 17. 01:05
반응형
문제
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어��
www.acmicpc.net
풀이
인접리스트 adj와 visited 배열을 통해 bfs로 풀었다.
마지막에 1을 빼준건 1번 컴퓨터를 제외하기 위함
import sys
from collections import deque
# N: 노드 수 / M: 엣지 수
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
# 인접 리스트
adj = [[] for _ in range(N)]
visited = [0 for _ in range(N)]
# 인접 리스트 채우기
for _ in range(M):
x, y = map(int, sys.stdin.readline().split(" "))
adj[x-1].append(y-1)
adj[y-1].append(x-1)
queue = deque()
queue.append(0) # 1번 컴퓨터
visited[0] = 1
count = 0
# bfs
while queue:
v = queue.popleft()
count += 1
# v와 인접한 모든 애들
for each in adj[v]:
if visited[each] == 0:
queue.append(each)
visited[each] = 1
print(count-1)
반응형