Python에서 돌로 강을 건널 수 있는지 확인하는 프로그램

돌이라고 하는 정렬된 숫자 목록이 있고 이것이 우리가 건너려고 하는 강에서 돌의 위치를 ​​나타낸다고 가정합니다. 강을 건너려면 마지막 돌에서 끝내야 합니다. 이제 각 단계에서 k가 마지막 점프의 거리인 곳에서 (k - 1, k 또는 k + 1) 단계 앞으로 이동할 수 있습니다. 강을 건널 수 있는지 없는지 확인해야 합니다.

따라서 입력이 [0, 1, 3, 4, 5, 6, 8, 9, 13]과 같으면 출력은 True가 됩니다. 0에서 시작한 다음 1단위 점프하여 돌로 이동할 수 있기 때문입니다. 1, 2 유닛 3 이동, 2 유닛 5 이동, 3 유닛 8 이동, 마지막 5 유닛 이동 13, 여기가 최종 장소입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• start :=A[0], end :=A의 마지막 요소
• A :=A의 모든 고유 요소 집합
• check() 함수를 정의합니다. 이것은 pos:=start, prev:=0
이 걸립니다.
• pos가 end와 같으면
  • 참 반환
• [prev - 1, prev, prev + 1]의 각 점프에 대해 do
  • 점프>=1이면
    • next_pos :=점프 + 위치
    • next_pos가 A에 있고 check(next_pos, jump)가 true이면
      • 참 반환
• 거짓을 반환
• 메인 메소드 호출에서 check() 및 반환 결과

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, A):
      start, end = A[0], A[-1]
      A = set(A)
      def check(pos=start, prev=0):
         if pos == end:
            return True
         for jump in [prev - 1, prev, prev + 1]:
            if jump >= 1:
               next_pos = jump + pos
               if next_pos in A and check(next_pos, jump):
                  return True
         return False
      return check()
ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))

입력

[0, 1, 3, 4, 5, 6, 8, 9, 13]

출력

True