2606 바이러

1. 문제

문제는 링크에 들어가면 볼 수 있다.

2606 바이러스

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    #컴퓨터는 서로 연결되어있으므로.
    graph[a].append(b)
    graph[b].append(a)

for i in range(1,N+1):
    graph[i].sort()

visited = [False for _ in range(N+1)]

def BFS(graph,V,visited):
    q = deque()
    q.append(V)
    while q :
        now = q.popleft()
        visited[now] = True
        for i in graph[now] :
            if not visited[i]:
                visited[i] = True
                q.append(i)

    return visited


updated_visited = BFS(graph,1,visited)
print(sum(updated_visited)-1) # 1은 빼야한다.

3. 문제 풀이

본 문제의 핵심은 “1번 컴퓨터와 연결된 컴퓨터들을 찾기”이다.

BFS를 통해서 주변에 연결된 노드들을 확인하고, 연결되어있는 여부를 체크하는 리스트를 만들어서 True,False를 기록한다. 그렇게 되면 1번에서 갈 수 있는 노드들만을 반환하게 되는데, 이것은 1번과 연결된 컴퓨터들을 뜻한다. boolean은 1,0으로도 표현가능하므로, 단순히 sum()함수를 통해 결과를 도출할 수 있다.