글 읽기 - 파이썬 - bfs 이용했는데 반례를 못찾겠습니다,,

cocojeun 2년 전 0

0 부터 100000까지 범위지정을 안해줘서인가 했는데 해줘도 안되네요 ㅠ

그냥 틀렸습ㄴㅣ다가 떠버리는..

from collections import deque

n, k = map(int,input().split())
visited =[n] #갔던 위치
q= deque([(n,0)])

while q:
    v, t = q.popleft() #위치와 이동횟수
    #print("({},{})".format(v,t))
    a = [2*v,v+1,v-1]
    for way in a:
        if way ==k:
            print(t+1)
            q.clear()
            break
        if way in visited or way<0 or way>100000:
            continue
        else:
            q.append((way,t+1))
            visited.append(way)

nahwasa 2년 전 1

반례입니다.

1 1

cocojeun 2년 전 1

@nawhasa 맞네요! 그런데 이젠 시간초과가 뜨네요 하하 ^^.. 감사합니다!

nahwasa 2년 전 1

visited를 []로 하셔서 그렇습니다.

in 연산에 시간이 매우 많이 걸립니다.

그래도 파이썬 보다는 pypy가 좀 더 최적화가 잘되있어서 pypy로는 통과가 되기는 하나, 7초나 걸리네욬ㅋㅋㅋ

[] 대신 set으로 살짝 변경해봤습니다. 200ms 정도 나오네요.

from collections import deque

n, k = map(int,input().split())
if n==k :
    print(0)
    exit(0)
visited =set() #갔던 위치
q= deque([(n,0)])

while q:
    v, t = q.popleft() #위치와 이동횟수
    a = [2*v,v+1,v-1]
    for way in a:
        if way ==k:
            print(t + 1)
            q.clear()
            break
        if way in visited or way<0 or way>100000:
            continue
        else:
            q.append((way,t+1))
            visited.add(way)

cocojeun 2년 전 1

@nawhasa 세상ㅇ ㅔ 정말 감사합니다

큰거 알아가네요 ,,,, 당연히 in 연산은 리스트에서 한다고 생각했어요

셋이 더 빠르군요 !!!

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

문제

문제

출처

ICPC

파이썬 - bfs 이용했는데 반례를 못찾겠습니다,,

cocojeun 2년 전 0

nahwasa 2년 전 1

cocojeun 2년 전 1

nahwasa 2년 전 1

cocojeun 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말