[백준 19538] 루머 (Gold 4)
문제
https://www.acmicpc.net/problem/19538
접근
BFS로 해결
1) times라는 리스트를 Node 수의 크기만큼 만들고 -1로 초기화한다.
2) 과반수 여부를 확인하기 위해 Node에 연결된 Node들을 탐색한다. 이 때 times의 값이 -1이 아닌 것만 세준다.
3) 과반수를 넘으면 rumors라는 리스트에 Node 번호를 넣어준다.
4) queue에 값이 없는 경우가 1초가 지난 경우. 이 때 rumors 안에 있는 값에 대해 시간을 업데이트 해준다.
Code
import sys
from collections import defaultdict, deque
def bfs():
q = deque()
for arr in arrs:
times[arr] = 0
q.append(arr)
rumors = []
while q:
curr = q.popleft()
for next_node in graph[curr]:
t, cnt = 0, 0
if times[next_node] == -1:
for i in graph[next_node]:
if times[i] != -1:
t += 1
if len(graph[next_node]) <= 2 * t:
rumors.append(next_node)
if not q:
for rumor in rumors:
if times[rumor] == -1:
times[rumor] = times[curr] + 1
q.append(rumor)
rumors = []
n = int(sys.stdin.readline())
graph = defaultdict(list)
for i in range(1, n + 1):
graph[i].append(list(map(int, sys.stdin.readline().split())))
graph[i] = graph[i][0][:-1]
m = int(sys.stdin.readline())
arrs = list(map(int, sys.stdin.readline().split()))
times = [-1] * (n + 1)
bfs()
print(*times[1:])
여담
4)를 생각 못하다가 어찌저찌 생각해서 풀었다
Author And Source
이 문제에 관하여([백준 19538] 루머 (Gold 4)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@daehoon12/백준-19538-루머저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)