[백준/파이썬] 2606번 바이러스 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2606번 바이러스
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

1번 컴퓨터와 연결된(직접 또는 간접) 모든 컴퓨터가 바이러스에 감염됩니다. 전체 네트워크 연결 정보가 주어질 때, 1번을 제외한 감염 컴퓨터 수를 구하면 됩니다.

코드

n = int(input())
coms = []
for _ in range(int(input())):
    coms.append(tuple(map(int, input().split())))
infected = {1}

i = 0
flag = False
while True:
    if len(coms) == 0 or i + 1 == len(coms) and not flag: break
        
    if coms[i][0] in infected:
        infected.add(coms[i][1])
        coms.pop(i)
        flag = True
    elif coms[i][1] in infected:
        infected.add(coms[i][0])
        coms.pop(i)
        flag = True
    else: i += 1

    if i == len(coms) and flag:
        i = 0
        flag = False
        
print(len(infected)-1)

설명

infected 집합에 감염된 컴퓨터를 유지하고, 간선 목록을 반복 순회하면서 한쪽이라도 감염된 간선은 반대쪽도 감염 처리합니다.

• 새 감염이 발생하면 처음부터 다시 순회
• 더 이상 감염 확장이 없으면 종료

최종적으로 len(infected) - 1이 정답입니다.

---

• 백준 문제풀이 전체 목록 보기

---