[백준] 1697번: 숨바꼭질 - python

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

아래는 첫번째로 열심히 푼 코드다. 

 

from collections import deque

n , m = map(int, input().split())

ch = [0] * (m+1)
dis = [0] * (m+1)

ch[n] = 1 #체크
dis[n] = 0

dq = deque()
dq.append(n)

while dq:
    now = dq.popleft() #빼서
    if now == m: #같으면 탈출
        break
    for next in (now-1, now+1, now*2): #상태트리 생성
        if 0<=next <=m and not ch[next]:  #방문 안햇고, next가 정상범위면       
            dq.append(next) #큐에 추가
            ch[next] = 1 #방문처리
            dis[next] = dis[now] + 1 #거리 증가 + 1
        
print(dis[m]) #거리 m 출력

 

그러나 바로 런타임 에러 (IndexError) 발생해서 확인해보니 ch[next]의 인덱스 번호를 체크해주지 않고 있어서 발생한 오류였다.

 

그래서 아래와 같이 다시 수정했다.

사실 이전에도 에러가 발생했는데 next를 체크하는 과정에서 0<next 로 해버려 0을 계산못해 틀렸다고 발생한거였다.

ch 리스트는 사실상 필요 없어도 계산은 되지만 코드의 효율성을 위해 생성하였다. 뿌리가 깊어지면 쓸때없는 연산이 늘어나기 때문이다.

 

from collections import deque

n , m = map(int, input().split())

ch = [0] * (100001)
dis = [0] * (100001)

ch[n] = 1 #체크
dis[n] = 0

dq = deque()
dq.append(n)

while dq:
    now = dq.popleft() #빼서
    if now == m: #같으면 탈출
        break
    for next in (now-1, now+1, now*2): #상태트리 생성
        if 0<=next<=100000:
            if ch[next] == 0:  #방문 안햇고, next가 정상범위면       
                dq.append(next) #큐에 추가
                ch[next] = 1 #방문처리
                dis[next] = dis[now] + 1 #거리 증가 + 1
        
print(dis[m]) #거리 m 출력

 

완성