[Python] 백준/BOJ 19538번: 루머 (Gold 4)

💻 Problem

문제 보러 가기

 

당신은 루머를 믿는가?

한 유명 심리학 실험에서는 사람들에게 두 개의 줄을 보여주고, 어떤 줄이 더 긴지 말하라 했다. 사실 한 사람을 제외하고 나머지는 실험자에 의해 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄을 더 길다고 말했다. 주변 모두가 같은 답변을 하자, 진짜 피실험자 또한 짧은 줄이 더 길다고 말했다. 이 실험은 사람들이 주변인의 영향을 강하게 받는다는 것을 보여주었는데, 루머도 이와 같다.

루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다.

매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다.

루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다.

이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.

 

💡 Approach

[예제 1]

0분 : 최초 유포자(1, 6번 사람)가 루머를 생성한다.
1분 : 1번 사람은 2, 3번 사람에게 루머를 퍼뜨린다. 2번 사람은 주변인 2명 중 1명이 루머를 믿고 있어 루머를 믿게 된다. 3번 사람은 주변인 3명 중 1명만 루머를 믿기 때문에, 루머를 믿지 않는다. 6번 사람은 루머를 퍼뜨릴 주변인이 없다.
2분 : 1, 2번 사람은 3번 사람에게 루머를 퍼뜨린다. 인접한 3명 중 절반 이상인 2명이 루머를 믿고 있어, 3번 사람도 2분부터 믿기 시작한다.
3분 : 3번 사람은 4번 사람에게 루머를 퍼뜨린다. 4번 사람이 믿기 시작한다.
4분 : 5번 사람도 루머를 믿게 된다. 7번 사람은 이후 충분한 시간이 지나도 루머를 믿지 않는다.

 

---

 

입력받은 주변인 정보 바탕으로 인접리스트를 만든다.

최초 유포자를 시작으로 루머를 퍼뜨린다.

루머를 퍼뜨리는 것은 bfs로 구현한다.

 

즉, 최초 유포자 index를 큐에 넣고 bfs를 시작한다.

현재 탐색 중인 사람의 주변인 중 아직 루머를 접하지 못한 사람에게 루머를 전한다.

 

루머를 접한 주변인은 자신의 주변인의 절반 이상이 루머를 믿고 있다면 본인도 루머를 믿고 이어서 탐색한다.

 

✏️ Solution

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

# 주변인의 절반 이상이 루머를 믿는지
def is_believe(i, t):
    cnt = 0
    for c in graph[i]:
        # 본인보다 먼저 루머를 믿은 주변인 세기
        if time[c] != -1 and time[c] < t:
            cnt += 1
    return cnt >= len(graph[i]) / 2

def spread_rumor():
    queue = deque()

    for s in spreader:
        time[s] = 0
        queue.append((s, 0))

    while queue:
        cur, t = queue.popleft()

        for next in graph[cur]:
            if time[next] == -1 and is_believe(next, t + 1):
                time[next] = t + 1
                queue.append((next, t + 1))

N = int(input()) # 사람의 수
graph = [[] for _ in range(N + 1)]

# 주변인 정보 바탕으로 그래프 만들기
for i in range(1, N + 1):
    graph[i] = list(map(int, input().split()))[:-1] # 주변인

M = int(input()) # 최초 유포자의 수
spreader = list(map(int, input().split())) # 최초 유포자의 번호
time = [-1] * (N + 1) # 루머를 처음 믿기 시작한 시간

spread_rumor()
print(*time[1:])

처음에는 매번 현재 탐색하려는 사람(cur)의 모든 주변인을 순회하며 검사(is_believe)했더니 시간이 오래 걸렸다.

is_believe에서는 주변인을 한 명씩 살펴보며 루머를 믿는 사람의 수를 센다.

(솔루션 적으려니까 is_believe가 문법적으로 말이 안 되긴 하는데.. 넘어갈게욥 ㅠㅋ)

 

통과는 하는데 다른 사람들이 제출한 코드보다 너무 오래 걸리길래 루머 전파 조건을 매번 계산하지 않고 믿은 주변인의 수를 리스트로 관리하는 식으로 최적화했다. (아래 코드)

 

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

def spread_rumor():
    queue = deque()

    for s in spreader:
        time[s] = 0
        queue.append(s)

    while queue:
        cur = queue.popleft()

        for next in graph[cur]:
            if time[next] == -1:
                believe[next] += 1

                if believe[next] >= len(graph[next]) / 2:
                    time[next] = time[cur] + 1
                    queue.append(next)

N = int(input()) # 사람의 수
graph = [[] for _ in range(N + 1)]

# 주변인 정보 바탕으로 그래프 만들기
for i in range(1, N + 1):
    graph[i] = list(map(int, input().split()))[:-1] # 주변인

M = int(input()) # 최초 유포자의 수
spreader = list(map(int, input().split())) # 최초 유포자의 번호
time = [-1] * (N + 1) # 루머를 처음 믿기 시작한 시간
believe = [0] * (N + 1) # 루머를 믿은 주변인 수

spread_rumor()
print(*time[1:])

루머를 믿은 주변인의 수를 저장할 리스트 believe를 선언해둔다.

queue에서 꺼낸 cur(현재 탐색하려는 사람)의 주변인을 순회한다.

주변인이 아직 루머를 접하지 않았다면 루머를 전할 것이다.

루머를 전해 들은 해당 주변인은 believe[next]를 1 증가시킨다.

believe[next]가 절반 이상이 될 때만 탐색을 진행한다.

 

예를 들어, 1번 사람과 연결된 2번 사람이 루머를 접하지 않았다면 2번 사람에게 루머를 전할 것이다.

2번 사람 입장에서도 1번 사람은 2번 사람의 주변인이다. 그렇기에 2번 사람의 믿은 주변인 수를 증가시킨다. (believe[2] + 1)

 

현재 기준 맞힌 사람(Python) 중에 2등이다.. 신기해