백준 2606번 : 바이러스 (Python)

문제 : www.acmicpc.net/problem/2606

2606번: 바이러스

 

풀이

큐를 이용하여 해결하였다.

com 리스트에 입력받은 쌍을 인덱스별로 넣는다.

이미 확인된 컴퓨터는 거치지 않도록 확인한 컴퓨터는 visited 리스트에 넣어준다.

 

que를 pop하고 확인된 컴퓨터인지 확인한다.

확인되지 않은 컴퓨터라면 visited에 해당 컴퓨터를 추가하고 결과값+1을 해준다.

그리고 큐에 해당 컴퓨터인덱스 리스트에 들어있는 연결 컴퓨터들을 모두 추가해준다.

 

입력받은 쌍을 넣을 때 양방향으로 넣어주어야 한다.

com[a].append(b)만 할 경우

2 1과 같이 입력을 받으면 인덱스 1 리스트에는 컴퓨터 2가 담기지 못한다.

이걸로 한번에 AC를 받지 못했다.

 

from collections import deque

N = int(input())                                   # 입력
com = [[] for i in range(N+1)]
M = int(input())
for _ in range(M):
    a, b = map(int, input().split())
    com[a].append(b)
    com[b].append(a)

que = deque()                                      # 초기화
que.append(1)
result = -1
visited=[]

while que:                                         # 실행
    n = que.popleft()
    if n in visited:
        continue
    visited.append(n)
    result +=1
    
    for i in com[n]:
        que.append(i)


print(result)