퍼져나갈 수 있는지를 묻고 있지만 도달할 수 있는지를 계산해야하는 BFS

19538번: 루머

 

최초 루머 유포자에서 시작해서 매분마다 주변인에게 루머를 퍼뜨리는데

 

해당 사람은 주변인의 절반 이상이 루머를 믿고 있다면 루머를 믿게 된다

 

충분한 시간이 지난 후 각 사람들이 처음 루머를 믿기 시작하는 시간을 모두 구한다

 

-------------------------------------------------------------------------------------------------------------------------------------------

 

단순하게 생각해서 유포자부터 큐에 넣어서 BFS를 수행해가지고,

 

방문가능한 정점에 방문해서 해당 정점의 주변 정점들 중 루머를 믿고 있는 정점 수를 찾고

 

그 정점 수가 주변 정점들 수의 절반 이상이면 해당 정점은 루머를 믿는 정점이 되고,

 

그때 최초 시간을 표시해두면 된다

 

라고 생각하고 접근하는데 N <= 20만이다보니 쉽지 않다

 

특정 정점에 방문해서 해당 정점 중 주변 정점들이 루머를 믿고 있는 정점 수를 찾는 과정이 O(N)이고

 

BFS를 O(N)에 하면 O(N^2)이 된다

 

어떻게 루머를 믿고 있는 정점 수를 O(1)에 찾는다고 하더라도

 

매 분마다 정점을 방문해봐서 루머를 믿게 되는 정점들을 모두 찾고 

 

이들을 업데이트 하다보니 O(N^2)이 되는

 

while queue:
    
    z = len(queue)

    trust = []

    for _ in range(z):

        x,c = queue.popleft()

        find = False

        for v in graph[x]:
            
            if answer[v] == -1:
                
                find = True
                count = 0

                for u in graph[v]:

                    if answer[u] >= 0:

                        count += 1

                if count >= len(graph[v])/2:
                    
                    trust.append(v)
    
        if find:
            
            queue.append((x,c+1))

    for v in trust:
        
        answer[v] = c+1
        queue.append((v,c+1))

print(*answer[1:])

 

 

이 문제는 루머를 퍼뜨리는 방향이 아니라 정점이 루머를 받아들인다고 생각해서 하면 O(N)에 가능한데

 

큐에 루머를 믿고 있는 정점을 담고

 

큐의 정점이 BFS로 주변 정점을 방문하면 루머를 각 주변 정점으로 퍼뜨리는 건데

 

 

 

 

X가 루머를 믿고 있는 정점일때 여기서부터 BFS로 그래프를 탐색하면 y정점에 방문하는데

 

아직 방문하지 않은 정점이라면 y를 방문하게 되는 정점의 수를 찾는다

 

y를 방문하게 되는 정점의 수는 바꿔 말하면 y 주변 정점중 루머를 믿고 있는 정점이 된다

 

따라서 큐를 모두 비우면 한번의 BFS로 y를 방문하게 되는 정점의 수를 알 수 있고

 

이때 y를 방문하게 되는 정점의 수가 y 주변 정점의 수 절반 이상이면 y는 루머를 믿게 되므로,

 

y를 다시 큐에 넣고 방문 처리하면 된다

 

매 분마다 BFS를 수행해야하니까 예전에 배운 테크닉 queue의 길이를 구해서 

 

매번 큐의 길이만큼 반복하는 식으로

 

while queue:
    
    z = len(queue)

    c += 1

    for _ in range(z):
    
        x = queue.popleft()

        for v in graph[x]:
        
            if visited[v] == 0:
                
                count[v] += 1
    
    for i in range(1,n+1):
        
        if visited[i] == 0:
            
            if count[i] > 0 and count[i] >= len(graph[i])/2:
                
                queue.append(i)
                visited[i] = 1
                answer[i] = c
        
print(*answer[1:])

 

 

처음에 1번과 6번을 큐에 담고 큐의 길이는 2니까 1분때는 2만큼만 반복함

 

1번을 빼서 주변 정점을 방문

 

2번과 3번 정점 각각은 1분에는 주변 정점 중 루머를 믿는 정점은 1번 하나라는 뜻

 

6번은 방문할 수 있는 정점이 없고

 

이게 끝나면 1,2,3,4,5,6,7 정점 중 아직 방문하지 않은 정점중에서

 

루머를 믿고 있는 정점의 수가 주변 정점중 절반 이상인 정점을 찾는데 2번 정점이 이에 해당하므로,

 

2번 정점은 이제 루머를 믿게 된다

 

 

 

그러면 큐에 넣어야할 정점은?

 

1번 정점, 2번 정점?

 

그렇지 않다

 

1번 정점은 이미 3번 정점에 루머를 퍼뜨렸으니 3번 정점은 주변 정점중 루머를 믿고 있는 정점이 1개 있다는걸 알고 있다

 

count[3] = 1

 

2번 정점만 큐에 넣고 2분 때 BFS를 수행하면 count[3] = 2가 된다는 거임

 

그러면 이 BFS가 끝나면 이제는 3번 정점이 주변 정점 3개중 2개가 루머를 믿으므로 3번 정점이 조건에 해당하고

 

3번 정점을 큐에 넣는다

 

 

 

근데 이렇게 하면 시간초과더라

 

생각해보니까 매번 count를 세면서 순간 count[v] >= len(graph[v])/2이면 큐에 넣으면 되겠더라

 

애초에 문제가 count[v]를 정확히 구하는게 아니거든

 

while queue:
    
    z = len(queue)

    c += 1

    for _ in range(z):
    
        x = queue.popleft()

        for v in graph[x]:
        
            if visited[v] == 0:
                
                count[v] += 1
                
                if count[v] >= len(graph[v])/2:
                    
                    queue.append(v)
                    visited[v] = 1
                    answer[v] = c
                    
print(*answer[1:])

 

 

이러면 뒤에 O(N)도는게 없어져서 시간안에 되나봐

 

뒤에 O(N)있으면 O(N^2)에 가까워지는듯? 흠

 

아무튼 핵심은 목표 정점이 루머를 퍼뜨리는게 아니라 루머를 받아들인다는 느낌으로 풀어야 풀 수 있다는거

 

from collections import deque
from sys import stdin

n = int(stdin.readline())

graph = [[] for _ in range(n+1)]

for i in range(1,n+1):

    A = list(map(int,stdin.readline().split()))
    
    for j in range(len(A)-1):

        graph[i].append(A[j])

m = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

answer = [-1]*(n+1)
visited = [0]*(n+1)
count = [0]*(n+1)

queue = deque([])

for i in range(m):
    
    answer[A[i]] = 0
    queue.append(A[i])
    visited[A[i]] = 1

c = 0

while queue:
    
    z = len(queue)

    c += 1

    for _ in range(z):
    
        x = queue.popleft()

        for v in graph[x]:
        
            if visited[v] == 0:
                
                count[v] += 1
                
                if count[v] >= len(graph[v])/2:
                    
                    queue.append(v)
                    visited[v] = 1
                    answer[v] = c
                    
print(*answer[1:])