Coding - Algo/python
[백준] 1697번:숨바꼭질 (python 파이썬)
jainn
2021. 2. 13. 00:47
728x90
문제
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
계속 indexerror 가 뜨길래 한참을 고민했는데
두번 째 if문에서 i의 범위를 i<=100000 로 해줬더니 발생한 문제 !!
-1, -2, -3.. 일때도 배열 인덱스 값으로 넣어줬으니 당연히 indexerror가 뜨는 것이었다 ㅠㅠ
num배열에 방문표시를 하며 단계적으로(bfs) 방문해서 결과값을 출력하게 했다 !
소스코드
from collections import deque
def bfs():
ans = -1
que = deque()
que.append(n)
while que:
ans+=1
for _ in range(len(que)):
x = que.popleft()
if x == k:
return ans
for i in (x-1, x+1, x*2):
if 0<=i<=100000 and num[i]==0:
num[i]=1
que.append(i)
n, k = map(int, input().split())
num = [0]*100001
num[n]=1
print(bfs())반응형