문제 소개
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 현재 인덱스 i에 있을 때, 목표 위치가 리스트 범위 안에 존재하는 경우에 한해 i + nums[i] 또는 i − nums[i]로 점프할 수 있습니다. 우리가 구해야 할 것은, 입력 순서를 그대로 유지하면서 자기 자신과 패리티(홀수·짝수 여부)가 다른 값에 도달하기 위해 필요한 최소 점프 횟수입니다. 아무리 점프를 반복해도 패리티가 다른 숫자에 도달할 수 없다면 결과는 −1로 설정합니다.
예를 들어, 입력이 numbers = [7, 3, 4, 5, 6, 9, 6, 7]이라면 출력은 [−1, 1, 2, −1, −1, −1, 1, −1]이 됩니다. 인덱스 1의 값 3은 한 번의 점프로 값 6(짝수)이 있는 인덱스 4에 도달할 수 있으므로 1이고, 인덱스 2의 값 4는 두 번의 점프를 거쳐야 홀수에 닿으므로 2입니다.
접근 방법: 너비 우선 탐색(BFS)
이 문제는 최소 점프 횟수를 구하는 전형적인 최단 경로 문제이므로 BFS가 적합합니다. 각 시작 인덱스마다 BFS를 수행하면, 처음으로 패리티가 다른 값에 도달한 시점의 거리가 곧 최소 점프 횟수가 됩니다.
풀이 단계
- bfs(i) 함수를 정의합니다.
- q := (i, 0) 쌍으로 초기화된 덱(deque)
- seen := 방문 여부를 기록할 빈 집합(set)
- q가 빌 때까지 반복:
- (j, d) := q의 맨 앞 요소를 꺼내고 제거
- j를 seen에 추가
- (nums[i] + nums[j]) % 2가 0이 아니면(패리티가 다르면) d를 반환
- k ∈ [j + nums[j], j − nums[j]]의 각 값에 대해:
- 0 ≤ k < len(nums)이고 k가 seen에 없다면 (k, d + 1)을 q의 뒤에 삽입
- 끝까지 찾지 못하면 10^10을 반환 (사실상 무한대 값)
- 메인 로직:
- ans := 빈 리스트 생성
- i를 0부터 len(nums) − 1까지 반복:
- x := bfs(i)
- x < 10^10이면 ans에 x를 추가하고, 그렇지 않으면 −1을 추가
- ans 반환
구현 예제
from collections import deque
class Solution:
def solve(self, nums):
def bfs(i):
q = deque([(i, 0)])
seen = set()
while q:
j, d = q.popleft()
seen.add(j)
if (nums[i] + nums[j]) % 2:
return d
for k in [j + nums[j], j - nums[j]]:
if 0 <= k < len(nums) and k not in seen:
q.append((k, d + 1))
return 10 ** 10
ans = []
for i in range(len(nums)):
x = bfs(i)
ans.append(x if x < 10 ** 10 else -1)
return ans
ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))입력
numbers = [7, 3, 4, 5, 6, 9, 6, 7]
출력
[−1, 1, 2, −1, −1, −1, 1, −1]
복잡도 분석
각 인덱스마다 BFS를 독립적으로 수행하므로 시간 복잡도는 O(n²)입니다. n개의 시작점 각각에서 최대 n개의 노드를 방문할 수 있기 때문입니다. 공간 복잡도는 큐와 방문 집합에 의해 O(n)입니다. 만약 성능 최적화가 필요하다면 역방향 BFS나 그래프 사전 구축 등의 기법으로 개선할 수 있습니다.