BOJ 19538번: 루머

www.acmicpc.net/problem/19538

19538번: 루머

아이디어:

큐를 두개를 사용하여서 루머를 믿는 사람을 저장하는 큐 A와 A의 인접한 노드들을 저장하는 큐 B로 나눈다.

A의 요소들을 pop하면서 시간을 저장하고 해당 요소의 인접리스트를 B에 저장한다. A의 요소가 모두 비게 되면 시간이 +1되는 것이다.

그리고 B의 요소들을 pop하면서 루머에 감염되었는지 여부를 판단하고 감염된 노드만 A에 다시 추가한다.

 

처음에는 최초유포자들을 시작으로 각각 bfs를 한다는 생각으로 풀었는데, 이게 말이 안된다는 걸 깨닫고 구글링을 좀 해봤다.. 그러다가 큐를 두 개 사용한다는 말에 힌트를 얻어 풀었다. 파이썬으로 제출하면 시간초과가 나고 pypy로 제출하면 통과한다.

import sys
from collections import deque
N = int(sys.stdin.readline())
graph = [[]for _ in range(N+1)]
ans = [1000000]*(N+1)

#입력
for i in range(1,N+1):
    graph[i]=list(map(int, sys.stdin.readline().split()))
    graph[i].pop()
M = int(sys.stdin.readline())
first = list(map(int, sys.stdin.readline().split()))

qA = deque() #루머에 감염된 노드
qB = deque() #큐A의 노드에 인접한 노드

for i in first:
    qA.append([i,0]) #최초 유포자
    
while(qA):
    while(qA):
        n = qA.popleft()
        ans[n[0]] = min(ans[n[0]],n[1]) #최솟값을 갖도록 설정해야 함.

        for i in graph[n[0]]:
            if (ans[i]==1000000):
                qB.append([i,n[1]+1])
    while(qB):
        n = qB.popleft()
        cnt = 0
        for i in graph[n[0]]:
            if (ans[i]!=1000000): cnt+=1
        if (cnt>=(len(graph[n[0]])+1)//2):
            qA.append(n)


for i in range(1,N+1):
    if (ans[i]==1000000): print(-1, end=" ")
    else: print(ans[i], end=" ")