숫자로 이루어진 리스트 nums와 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 인덱스 k에서 시작하며, 현재 위치한 인덱스 i에서는 정확히 nums[i]칸만큼 왼쪽 또는 오른쪽으로 점프할 수 있습니다. 목표는 리스트의 마지막 인덱스까지 도달할 수 있는지 확인하는 것입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해봅시다.
nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2
이 경우 출력은 True가 됩니다. 인덱스 2에서 시작하면 값이 2이므로 인덱스 4로 점프할 수 있고, 인덱스 4의 값이 3이므로 마지막 인덱스 7까지 한 번에 도달할 수 있기 때문입니다.
해결 접근 방법
이 문제는 그래프 탐색(DFS/BFS) 아이디어로 풀 수 있습니다. 각 인덱스를 노드로 보고, nums[i]만큼 떨어진 왼쪽·오른쪽 인덱스를 인접 노드로 생각하면 됩니다. 이미 방문한 인덱스를 다시 탐색하지 않도록 하여 무한 루프를 방지합니다.
구체적인 알고리즘은 다음과 같습니다.
- 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 이면 up을 tovisit에 추가합니다.
- down >= 0 이면 down을 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