[백준][Python] 19538번 루머 - 그래프,BFS

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

 

Python

from collections import deque
import sys
input = sys.stdin.readline

n = int(input().rstrip())
p = []
connect = [set() for _ in range(n)]
for i in range(n):
    p.append(list(map(lambda x: int(x)-1, input().split()))[:-1])
    for x in p[-1]:
        connect[i].add(x)
        connect[x].add(i)

m = int(input().rstrip())
rumer = list(map(lambda x: int(x)-1, input().split()))
dist = [[0, 0] for _ in range(n)]
for i in rumer:
    dist[i][1] = n
    dist[i][0] = 1

q = deque(rumer)
while q:
    pos = q.popleft()
    for x in p[pos]:
        dist[x][1] += 1
        if len(connect[x])/2 <= dist[x][1]: # 과반수 이상인지 확인
            if dist[x][0] == 0 or dist[x][0] > dist[pos][0]+1:
                dist[x][0] = dist[pos][0]+1
                q.append(x)

print(" ".join(map(str, [d[0]-1 for d in dist])))