문제 소개
강을 건너기 위해 밟고 지나갈 수 있는 돌들의 위치가 정렬된 리스트 형태로 주어진다고 가정해 봅시다. 강을 건너려면 반드시 마지막 돌에 도착해야 하며, 매 단계마다 직전 점프 거리를 k라고 할 때 k-1, k, k+1 중 하나의 거리만큼 앞으로 점프할 수 있습니다. 우리가 확인해야 할 것은 이러한 규칙 안에서 강을 끝까지 건널 수 있는지 여부입니다.
예를 들어 stones = [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의 고유한 원소들로 이루어진 집합(set)으로 변환합니다. 이렇게 하면 특정 위치에 돌이 있는지 O(1) 시간에 확인할 수 있습니다.
- check() 함수를 정의합니다. 초기값은 pos := start, prev := 0입니다.
- pos가 end와 같으면 True를 반환합니다.
- [prev - 1, prev, prev + 1]의 각 점프 거리에 대해 다음을 수행합니다.
- jump >= 1이면 next_pos := jump + pos를 계산합니다.
- next_pos가 집합 A에 존재하고 check(next_pos, jump)가 True이면 True를 반환합니다.
- 모든 경우를 확인했음에도 도달하지 못하면 False를 반환합니다.
- 메인 메서드에서 check()를 호출하고 그 결과를 반환합니다.
Python 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
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
성능 개선 팁
위 재귀 구현은 최악의 경우 지수적인 시간 복잡도를 가질 수 있습니다. (현재 위치, 직전 점프 거리) 조합을 딕셔너리나 functools.lru_cache로 메모이제이션하면 이미 탐색한 상태를 건너뛰어 실행 속도를 크게 향상시킬 수 있습니다. 또한 인접한 두 돌 사이의 간격이 계속 커져서 어떤 점프로도 도달할 수 없는 경우를 미리 걸러내는 가지치기(pruning) 기법도 유용하게 활용할 수 있습니다.