백준 19538. 루머

tose33 2023. 10. 5. 15:22

19538번: 루머

예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$

www.acmicpc.net

최초 유포자를 q 에 넣고 bfs 를 돌리면 된다.

bfs 에서 사람을 큐에 넣을지 말지 판단은

1. 아직 루머를 믿지 않고

2. 그 사람의 주변인중 루머를 믿는 사람 수가 절반 이상