숫자 리스트 nums와 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 인덱스 k에서 출발하며, 임의의 인덱스 i에 있을 때 정확히 nums[i]칸만큼 왼쪽 또는 오른쪽으로 점프할 수 있습니다. 이때 리스트의 마지막 인덱스에 도달할 수 있는지 판별하는 것이 이 글의 목표입니다.
예를 들어 입력이 nums = [0, 0, 2, 1, 3, 3, 1, 1], k = 2라면 결과는 True입니다. 인덱스 2에서 시작해 값 2만큼 점프하여 인덱스 4로 이동하고, 다시 값 3만큼 점프하여 마지막 인덱스 7에 도달할 수 있기 때문입니다.
해결 접근 방법
이 문제는 그래프 탐색 알고리즘으로 해결할 수 있습니다. 각 인덱스를 하나의 노드로 생각하고, 현재 인덱스에서 점프해서 도달할 수 있는 인덱스들을 인접 노드로 간주하면 됩니다. 여기서는 스택을 활용한 깊이 우선 탐색(DFS) 방식으로 구현해 보겠습니다.
알고리즘의 동작 단계는 다음과 같습니다.
n:= nums의 크기visited:= 크기가 n이고 0으로 초기화된 리스트 (방문 여부 저장)tovisit:= 시작점 k를 담은 리스트 (탐색 대상 스택)- tovisit이 비어 있지 않은 동안 반복:
- i := tovisit에서 마지막 원소를 꺼냄(pop)
- i가 n-1(마지막 인덱스)이면 True 반환
- visited[i]가 아직 방문하지 않은 상태라면:
- visited[i] := 1로 방문 표시
- up := i + nums[i], down := i - nums[i] 계산
- up이 n보다 작으면 tovisit에 추가
- down이 0 이상이면 tovisit에 추가
- 반복이 모두 끝나면 마지막 인덱스에 도달할 수 없으므로 False 반환
방문 여부를 체크하는 이유는 같은 인덱스를 반복해서 탐색하는 무한 루프를 방지하기 위함입니다. 이 덕분에 전체 탐색이 선형 시간 안에 종료됩니다.
구현 예제
class Solution:
def solve(self, nums, k):
n = len(nums)
visited = [0] * n
tovisit = [k]
while len(tovisit) > 0:
i = tovisit.pop()
if i == n - 1:
return True
if visited[i] != 1:
visited[i] = 1
up = i + nums[i]
dn = i - nums[i]
if up < n:
tovisit.append(up)
if dn >= 0:
tovisit.append(dn)
return False
ob = Solution()
nums = [0, 0, 2, 1, 3, 3, 1, 1]
k = 2
print(ob.solve(nums, k))
입력
[0, 0, 2, 1, 3, 3, 1, 1], 2
출력
True
복잡도 분석
시간 복잡도: O(n) — 각 인덱스는 최대 한 번만 방문되므로 전체 탐색은 선형 시간에 완료됩니다.
공간 복잡도: O(n) — 방문 여부를 저장하는 배열과 탐색용 스택이 최대 n개의 원소를 가질 수 있습니다.