백준 문제(bfs) 질문입니다

조회수 1221회

백준 문제

from collections import deque

s, d = map(int, input().split())
q = deque()
q.append([s, 0])
chk = [True for i in range(200001)]
chk[s] = False

while q:
    t = q.popleft()
    if t[0] == d:
        print(t[1])
        exit()

    if chk[t[0] - 1] and t[0] - 1 <= 100000:
        q.append([t[0] - 1, t[1] + 1])
        chk[t[0] - 1] = False
    if chk[t[0] + 1] and t[0] + 1 <= 100000:
        q.append([t[0] + 1, t[1] + 1])
        chk[t[0] + 1] = False
    if chk[t[0] * 2] and t[0] * 2 <= 100000:
        q.append([t[0] * 2, t[1] + 1])
        chk[t[0] * 2] = False

자꾸 53퍼 에서 런타임 에러 떠요. 왜그러죠?

1 답변

  • if chk[t[0] - 1] and t[0] - 1 <= 100000:
    

    여기가 문제로 보이네요

    인덱스를 계속 감소하면서 탐색할텐데 t[0] - 1 이 음수가 될 수 있습니다

    파이썬은 음수 인덱싱도 가능하니 몇개의 테스트케이스에 대해서는 문제가 없어 보이지만 큐에 들어간 음수가

    t[0] * 2에 의해서 -200001 보다 작아지는 순간 인덱스에러가 납니다

    애초에 q에 들어간 t[0]의 값은 이미 100000이하 일 것이니

    t[0] - 1 <= 100000
    

    이라는 조건은 의미가 없습니다

    t[0] - 1 >= 0
    

    으로 수정하면 정답이 될 듯 합니다 : )

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)