[백준 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)를 생각 못하다가 어찌저찌 생각해서 풀었다