2606 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

내 풀이(맞춤)

from collections import deque

n = int(input())
m = int(input())

dic = {}
for i in range(m):
    a, b = map(int, input().split())
    if a not in dic:
        dic[a] = [b]
    else:
        dic[a].append(b)
    if b not in dic:
        dic[b] = [a]
    else:
        dic[b].append(a)

q = deque()
for i in dic[1]:
    q.append(i)

result = []
while q:
    t = q.popleft()
    if t not in result:
        result.append(t)
    if t in dic:
        for i in dic[t]:
            if i in result:
                continue
            q.append(i)

print(len(result)-1)

이 문제는 딕셔너리와 너비 우선 탐색을 활용하여 풀었다.

딕셔너리로 서로 연결된 컴퓨터를 표시한다. 근데 양방향 연결이라 양쪽 다 연결을 표시한다. 그리고 딕셔너리에 있는 집합을 큐로 옮긴다. 그리고 1로부터 연결된 컴퓨터를 result에 넣었다. 

마지막에 -1을 해서 출력하는 이유는 result에 1도 포함되어있는데 문제에선 1과 연결된 컴퓨터 중 감염된 것이 몇 개인지 물어봐서 1은 제외하고 세야하기 때문이다.