728x90
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
n = int(input()) # 컴퓨터 수
pair = int(input()) # 컴퓨터 쌍의 수
p = []
for _ in range(pair): # 정렬
a, b = input().split()
if a < b:
p.append([int(a), int(b)])
else:
p.append([int(b), int(a)])
p.sort()
if 1 != p[0][0]:
print(0)
else:
virus = [1]*n
result = [1]
cnt = 0
while 1:
if result == []:
break
x = result[0] # 쌍에 x 가 존재하는 지 비교
virus[x-1] = 0 # x 번 컴퓨터는 바이러스 전염됨
for i in range(len(p)):
if p[i] != 0 : # 비교하지 않은 쌍인 경우
if p[i][0] == x:
result.append(p[i][1])
p[i] = 0
elif p[i][1] == x:
result.append(p[i][0])
p[i] = 0
del result[0]
print(virus.count(0)-1) # 1번 빼고 전염된 개수 출력
반응형
'전.py' 카테고리의 다른 글
백준 2667 단지번호붙이기 (실패) (0) | 2020.12.12 |
---|---|
백준 2605 줄 세우기 (0) | 2020.12.12 |
백준 2607 비슷한 단어 (0) | 2020.12.12 |
백준 2608 로마 숫자 (0) | 2020.12.12 |
백준 1289 팰린드롬수 (0) | 2020.12.12 |