BOJ 2606번 - 바이러스

[백준 온라인 저지 링크]

2606번: 바이러스

[정답 코드 - Python]

from collections import deque

N = int(input())
T = int(input())

# connection : 컴퓨터 / infected : 감염여부
connection = [0]
infected = [False] * (N + 1)

# 초기 입력
for _ in range(T):
    connection.append(list(map(int, input().split())))


def DFS():
    s = []
    # 언제나 첫 번째 컴퓨터로 감염이 시작되어 초기값을 1로 잡은 모습입니다.
    s.append(1)
    while s:
        next_com = s.pop()
        infected[next_com] = True
        for i in range(1, T + 1):
            # 이 문제의 핵심이 되는 부분으로, 탐색이 무한순환에 빠지지 않기 위해
            # 다음번에 탐색할 컴퓨터가 감염되지 않았을 경우에만 스택에 추가합니다.
            if connection[i][0] == next_com and infected[connection[i]
                                                         [1]] == False:
                s.append(connection[i][1])
            if connection[i][1] == next_com and infected[connection[i]
                                                         [0]] == False:
                s.append(connection[i][0])


DFS()
# 1번 컴퓨터를 제외한 감염 컴퓨터의 수를 출력합니다.
print(infected.count(True) - 1)