백준 문제(bfs) 질문입니다
조회수 1215회
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
으로 수정하면 정답이 될 듯 합니다 : )
댓글 입력