[파이썬/python] 백준 - 19538 루머

문제

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

---

문제 설명

1.   최초 유포자부터 시작하여 루머를 퍼트린다.
2. 매 분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트린다.
   1. 이 때 주변인의 절반 이상이 루머를 믿고 있다면, 본인도 루머를 믿는다.
3. 사람들이 루머를 처음 믿기 시작하는 시간을 구한다.

 

---

풀이

문제만 읽어보았을 때는 단순 탐색의 냄새가 강렬하게 난다. 따라서 처음에는 단순 BFS로 접근했다가 문제를 찾았다. 문제의 핵심 포인트는 설명에 나와있다.

매 분 루머를 믿는 사람은 주변인에게 루머를 퍼트린다. 즉 루머를 믿는 사람만 퍼트리기 때문에 방문 탐색을 바로 진행하는 것이 아니라, 다음 사람이 루머를 믿게 될 때만 방문처리를 하고 다음 탐색 큐에 넣어주면 된다.

탐색 전 사람 별 몇 명을 넘어야 루머를 믿게 되는지 카운트를 해 놓은 후, 탐색을 진행할 때 마다 수를 늘려 루머를 믿을 수 있는지 없는지 검사했다.

1. 최초 mid 배열에 각 사람이 루머를 믿게 되는 주변인의 수를 계산한다.
2. 너비 탐색을 진행한다.
   1. 매 탐색마다 다음 사람의 주변인 수를 1씩 증가시킨다.
   2. 만약 루머를 믿게 되는 사람 수가 넘었다면, 현재 시간을 기록하고 다음 사람의 노드를 큐에 넣어준다.
3. 최종 결과 배열을 출력한다.

---

코드

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

N = int(input())
graph = [[] for _ in range(N+1)]
res = [[0,-1] for _ in range(N+1)]
mid = [0 for _ in range(N+1)]
for v1 in range(1,N+1):
    tmp = list(map(int,input().split()))[:-1]
    l = len(tmp)
    if l % 2 == 0 and l != 0:
        l = (l//2)-1 
    else:
        l = l//2
    mid[v1] = l
    for v2 in tmp:
        graph[v1].append(v2)

visited = [0 for _ in range(N+1)]
M = int(input())
queue = deque()
for v1 in list(map(int,input().split())):
    queue.append((v1,1))
    res[v1][0],res[v1][1] = [mid[v1]+1,0]
    visited[v1] = 1

def bfs():
    cost = 0
    while queue:
        v1,cost = queue.popleft()

        for v2 in graph[v1]:
            res[v2][0] += 1

            if res[v2][0] > mid[v2] and res[v2][1] == -1:
                res[v2][1] = cost
                queue.append((v2,cost+1))
                visited[v2] = 1 

bfs()
for i in range(1,N+1):
    print(res[i][1],end = ' ')

---

시간복잡도

• 단순 인접리스트 BFS 시간복잡도이다. $O(V + E)$
• 노드 V의 최댓값은 $2*10^5$, 간선 E의 최대값은 $10^6$이다.
• 약$ O(10^6)$정도의 시간복잡도가 소요된다.