글 읽기 - 파이썬 bfs 시간초과 질문입니다.

blanka 3년 전 0

bfs로 풀고 있습니다. 큐 없이 배열에 나올 수 있는 수를 모두 저장하며 가는 방식으로 풀었는데 시간초과가 나네요.

직접 실험해보니 100000을 넣었을 때 엄청나게 오래 걸리는데, 다른 방식이 떠오르지 않네요. 도와주시면 감사하겠습니다.

n,k=map(int,input().split())
a=[n]
sec=0
ind=0
lim=0
cnt=0
if k>=n:
    while not k in a:
        b=2*a[ind]
        if not b in a:
            a.append(b)
            cnt+=1
        b=b//2+1
        if not b in a:
            a.append(b)
            cnt+=1
        b-=2
        if b>=0 and not b in a:
            a.append(b)
            cnt+=1
        if k in a:
            sec+=1
            break
        if ind==lim:
            lim+=cnt
            cnt=0
            sec+=1
        ind+=1
    print(sec)
else:
    print(n-k)

shg9411 3년 전 0

리스트에서 in은 O(N)의 시간 복잡도를 가집니다.

이런 방식으로는 시간초과가 나올 수 밖에 없습니다.

큐를 사용하지 않으시는 이유가 있나요?

blanka 3년 전 0

그냥 전에 bfs 문제에서 큐를 쓰지 않고 푼 적이 있어서 한번 해봤는데 이번엔 잘 안되네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 bfs 시간초과 질문입니다.

blanka 3년 전 0

shg9411 3년 전 0

blanka 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말