[BOJ] 파이썬 19538번_루머

문제링크

해설

import sys
input = lambda:sys.stdin.readline()
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
    v =  list(map(int,input().split()))
    v.pop()
    graph[_ + 1] = v


m = int(input())
init = list(map(int,input().split()))

infected = [-1 for _ in range(n + 1)]
visited=  [ 0 for _ in range(n+1)]
queue = deque([])
for ini in init:
    queue.append((ini))
    infected[ini] = 0

while queue:
    current = queue.popleft()

    for next in graph[current]:
        visited[next] += 1
        if infected[next] == -1:
            cnt = 0
            if visited[next] * 2 >= len(graph[next]):
                queue.append(next)
                infected[next] = infected[current] + 1


print(*infected[1:])

어려웠던 문제. 단순히 bfs를 돌린다면 시간초과를 받는다. 문제의 조건인 주변인의 절반 이상이 루머를 믿을때 를 어떻게 적용시킬지 생각해보아야한다.

BFS 탐색중 어떤 정점을 방문한다는 것은, 인접한 루머신봉자가 방문을 했다는 의미이다.

이 방문횟수는 결국 주변인중 루머를 믿는 인간의 수가 되버린다.

이 방문한 횟수를 visited 배열에 count 해준다. 이 정보로 위의 조건들을 처리하면 통과.

감염된 주변인의 수를 체크하는 창의적인 방법을 배울 수 있었다.