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

문제

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

19538번: 루머

 

 

 

 

문제풀이

2개의 덱을 사용해서 풀었다.

 

처음 유포자를 시작으로 새로 루머를 믿는 사람들을 start 덱에 추가하여 덱이 빌 때까지 탐색을 진행했다.

 

새로 루머를 믿는 사람들의 time 값을 업데이트 해 줄 때에는 즉시 업데이트 해주는 것이 아니라,

따로 que라는 덱에 추가해서 해당 탐색이 끝난 이후에 업데이트를 해주었다.

즉시 업데이트 하는 경우, 다음 원소들의 탐색에 영향을 주기 때문이다.

 

 

코드

from collections import deque
n=int(input())
people=[]
for i in range(n):
    t=list(map(int,input().split()))
    t.pop()
    people.append(t)
people.insert(0,[])
m=int(input())
start=list(map(int,input().split()))

time=[-1]*(n+1)
for i in start:
    time[i]=0
##최초유포자 0으로 초기화
#1번부터 시작 유의**

start=deque(start)
que=deque([])
while(start):
    index=start.popleft()
    temp=people[index]
    move=[]
    for i in temp:
        count=0
        if time[i]!=-1:
            continue ##이전에 바뀜
        leng=len(people[i])
        for j in range(leng):
            if time[people[i][j]]!=-1:
                count+=1
        if leng>count*2:
            continue
        que.append(i)
    if not start:
        while(que):
            tmp=que.popleft()
            time[tmp]=time[index]+1
            start.append(tmp)

time.remove(time[0])
print(*time)

 

기타

코드에 특별한 이론이 필요한 것은 아니지만, 인덱스 처리 과정이 헷갈려서 코드 구현이 생각보다 오래걸렸다.

또, 처음에는 time값을 바로바로 업데이트 해주어서 그 이후 값들에 대한 차질이 생기기도 했고

입력 값들을 zero base라고 생각해서 이상한 값을 불러와서 계산하기도 했다😅😅