1234juwon   1년 전

양방향 BFS풀이로 써봤는데.....시간초과가 빨리 떠버리네요. 어떻게 고치면 될까요?

luckyandykang   1년 전

혹시 PyPy3으로 제출해보실 수 있을까요? PyPy3이 Python 3보다 훨씬 빠른 언어로 알려져 있습니다. 그래도 시간 초과가 발생하면 이 글에 다시 댓글을 달아 주시면 다시 확인해볼 수 있도록 하겠습니다.

1234juwon   1년 전

PyPy3로 제출했더니 틀렸습니다가 뜨네요. 혹시 다른 방법이 있을까요?

luckyandykang   1년 전

PyPy3은 Python 3와 작동 방식이 정확히 같은 언어로, PyPy3에서 틀렸습니다를 받았다면 알고리즘이 잘못된 것으로 보입니다. 저는 이 문제를 풀 때 한 방향으로만 BFS를 시행해서 풀이했는데, 단방향 BFS를 사용해보시는 것은 어떨까요?

luckyandykang   1년 전

추가로 rev_d 함수에서 소소한 오류(?)가 존재하는 것 같습니다. 본 코드에서는 rev_d의 인자에 값이 들어갔을 때 원래 값이 k인 경우와 5000 + k인 경우 중 k인 경우만을 순회합니다.

luckyandykang   1년 전

그리고 BFS를 시작할 때 초기값을 visited_b[n] = True, visited_f[ans] = True와 같이 처리해주어야 할 것 같습니다.

1234juwon   1년 전

아.. 네. 제가 처음에 단방향 BFS 시도해봤다가 계속 시간초과 떠서 양방향으로 바꾼 거였는데, 한번 다시 시도해보겠습니다. 

1234juwon   1년 전

단방향 코드 PyPy3로 넣어보니 해결되었습니다. 정말 감사드립니다!

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