[Python] 19538 루머

[Gold IV] 루머 - 19538

[문제 링크](https://www.acmicpc.net/problem/19538)

---

💻 문제 정의

최초 유포자로 부터 유포된 루머가 모든 주변인으로 퍼질 때, 각 사람들이 처음 루머를 믿게된(루머가 퍼진) 첫 시간을 출력하는 문제이다.

 

💡 접근 및 설계

BFS를 활용하여 문제를 접근하였다. 유포자는 자신과 인접한 사람에게 루머를 퍼뜨린다. 그리고 사람들은 자신의 인접한 사람의 절반 이상이 루머를 믿는다면 자신도 루머를 믿게 된다. 따라서 자신을 중심으로 주변인들 중 몇명이 루머를 믿는지 파악하는 것이 핵심이다.

 

✏️ 알고리즘 풀이

N = int(input())

graph = [[0]] 
for _ in range(N):
    rel = list(map(int, input().split()))
    graph.append(rel[:len(rel)-1])

M = int(input())

first = list(map(int, input().split()))

우선 입력 처리 부분이다. N명의 사람의 인접한 사람들을 graph에 저장한다. 이후 첫 번째 루머 유포자를 first 리스트로 받는다.

roumer = [False] * (N+1) # 루머를 믿는지 안밎는지 여부 저장 리스트
trust_me = [0] * (N+1) # 내 주변의 사람들이 루머를 얼마나 믿는지 여부 저장
time = [-1] * (N+1) # 루머가 퍼지는 시간

초기 세팅을 위해 다음과 같이 3개의 리스트를 정의하였다.

roumer리스트는 각 노드(사람)들이 루머를 믿는지 안믿는지 True/False로 나타낸다.

trust_me리스트는 내가 루머를 믿기 위해 주변 사람이 몇 명 루머를 믿는지 체크하는 리스트이다. 해당 값이 0이 된다면, 나는 루머를 믿게 된다.

time리스트는 내가 루머를 믿기 시작한 시점을 저장하는 리스트다.

def bfs(lst: list):
    Q = deque()

    for ix in lst:
        Q.append(ix)
        roumer[ix] = True
        time[ix] = 0

    for i in range(1, N+1):
        trust_me[i] = (len(graph[i])+1) // 2

    while Q:
        c = Q.popleft()

        for ix in graph[c]:
            trust_me[ix] -= 1
            if not roumer[ix] and trust_me[ix] <= 0:
                Q.append(ix)
                roumer[ix] = True
                time[ix] = time[c] + 1

BFS 코드이다. 최초 유포자를 중심으로 탐색을 시작한다.

먼저 최초 유포자들은 루머를 믿는다. 그리고 믿기 시작한 시점은 0분 이다.

이후 각 노드(사람)들은 자신의 인접한 사람들의 절반 이상이 믿어야 루머를 믿기 때문에 trust_me리스트에 다음과 같이 저장해주었다.

이후 while문을 통해 Q를 탐색한다. 루머를 믿는 사람들로 부터 탐색이 이어지기 때문에 trust_me[ix]는 1 감소하고, 이후 루머를 믿지 않으며 주변의 절반 이상의 사람이 루머를 믿는다면 자신도 루머를 믿게 된다. 그리고 Q에 추가하여 탐색을 이어간다. ix가 루머를 믿게된 시점은 c가 유포한 시점으로 부터 1분 후가 된다.

bfs(first)

print(*time[1:])

최종적으로 time리스트를 출력하게 되면 정답을 구할 수 있다.

 

🗒️ 제출 코드

# 19538 루머

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

def bfs(lst: list):
    Q = deque()

    for ix in lst:
        Q.append(ix)
        roumer[ix] = True
        time[ix] = 0

    for i in range(1, N+1):
        trust_me[i] = (len(graph[i])+1) // 2

    while Q:
        c = Q.popleft()

        for ix in graph[c]:
            trust_me[ix] -= 1
            if not roumer[ix] and trust_me[ix] <= 0:
                Q.append(ix)
                roumer[ix] = True
                time[ix] = time[c] + 1

N = int(input())

graph = [[0]] 
for _ in range(N):
    rel = list(map(int, input().split()))
    graph.append(rel[:len(rel)-1])

M = int(input())

first = list(map(int, input().split()))

roumer = [False] * (N+1)
time = [-1] * (N+1)
trust_me = [0] * (N+1)

bfs(first)

print(*time[1:])

---

💭 오늘의 회고

정말 오랜만에 알고리즘 문제를 풀었고, TIL을 작성한다.

다행이 오늘의 문제는 내가 제일 자신있어 하는 그래프 탐색 문제이다. 하지만 자신감과는 반대로 문제를 해결하지 못해 다른사람의 풀이를 참고하게 되었다.

초기 접근법은 내 주변의 루머를 믿는 사람과 이후 나에게 루머를 퍼뜨리는 사람 (trust_me[ix] + 1 )로 접근을 하였는데, 테스트 케이스는 모두 만족을 하였으나 정답이 나오진 않았다. 참고한 풀이를 보니 내가 접근한 방식과는 관점이 정반대였다.

나는 내 주변의 사람이 루머를 믿게 하려는 조건이었고, 그 사람의 풀이는 내가 루머를 믿기 위한 주변사람의 상태가 핵심이었다. 결국 이 관점 차이 하나로 문제 정답이 엇갈린 것 같다.

항상 알고리즘을 풀다 보면 같은 문제에도 여러가지 풀이법이 나오는데, 모든 풀이가 정답일 때도 있고 이 문제처럼 하나의 관점만이 정답일 수도 있다. 하나의 문제에 대해서 여러 관점에서 보는 것이 중요한 것 같다.