[BFS] -최소점프

최소 점프

현수는 놀이터에서 놀다가 집으로 가려고 합니다. 놀이터의 위치와 집의 위치가 수직선상의 좌표 점으로 주어집니다. 놀이터는 수직선상의 0지점입니다.
현수는 놀이터에서 스카이콩콩을 타고 점프를 하면서 집으로 이동하려고 합니다.
점프는 다음과 같은 규칙으로 합니다.

1) 현재 지점에서 앞으로 +1 만큼 점프이동할 수 있습니다.
2) 현재 지점에서 뒤쪽으로 -1 만큼 점프이동할 수 있습니다.
3) 현재 지점에서 앞쪽으로 +5 만큼 긴 점프이동을 할 수있습니다.
매개변수 home에 현수의 집의 위치가 주어지면 놀이터에서 집까지 최소 몇 번의 점프로 집에 도착할 수 있는지 최소 점프횟수를 구하여 반환하세요.

제한사항:
• 수직선의 좌표는 0부터 10,000까지입니다. • 현수가 집으로 반드시 갈 수 있습니다.

 

 

 

 

 

나의 코드

from collections import deque

def solution(home):
    answer = 0
    dq=deque()
    dq.append(0)
    L=0
    while dq:
        n=len(dq)
        for x in range(n):
            v=dq.popleft()
            for nv in [v-1,v+1,v+5]:
                if nv ==home:
                    return L+1
                dq.append(nv)
        L+=1
            

    
    return answer
            
print(solution(10))
print(solution(14))
print(solution(25))
print(solution(24))
print(solution(345))

결과 적으로 4개의 입력값에 대해서는 성공을 하였지만 마지막 입력값에 대해서는 5분이 지나고 결과값이 나오지 않았다.

즉, 시간 초과가 어엉엄~~청 나게 나고 있단느 뜻..

체크 배열에 대한 고민을 해보았지만 결국 마지막껀 해결 못했따..!

 

 

예시 1을 아래와 같이 BFS탐색 상태 트리로 그려보았따다.

큐를 사용하여 한 단계마다 L을 1씩 중가시켜 이동 횟수를 카운팅 하였다.

하지만 아래의 빨간 부분과 같이 중복 되거나 -1과 -2 와 같은 조건과 맞지 않는 거리에 대해 분기 처리를 해주지 않아 마지막 345 같은 큰 범위의 탐색은 실패 하였다 !

 

 

 

 

 

 

정답 코드

from collections import deque
def BFS(home):
    ch = [0] * 10001
    Q = deque()
    Q.append(0)
    ch[0] = 1
    L = 0
    while Q:
        n = len(Q)
        for i in range(n):
            x = Q.popleft()
         
            for nx in [x-1, x+1, x+5]:
                if nx >= 0 and nx <= 10000 and ch[nx] == 0:
                    if nx ==home:
                        return L+1
                    Q.append(nx)
                    ch[nx] = 1
        L += 1
                
 
def solution(home):
    answer = BFS(home)
    return answer
            
print(solution(10))
print(solution(14))
print(solution(25))
print(solution(24))
print(solution(345))

정답 코드를 보니 체크 배열과 nx의 범위를 0~10000사이로 제한을 하는 것을 놓쳤다..!

체크 배열이 가능 중요한것 같군.. 메모..