2020 November LeetCoding Challenge

문제

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

정수형 배열이 과 start 위치가 주어진다. index i 에 도착했을 경우
i + arr[i] 또는 i - arr[i] 로 점프 할수 있다.
arr[i] === 0 이 되는 위치에 도달 할 수 있는지를 구하는 문제.

코드

function canReach(arr: number[], start: number): boolean {

    const visited = new Map<string, boolean>();

    const jump = (idx: number): boolean => {

        if (arr[idx] === 0) {
            return true;
        }

        if (idx >= arr.length || idx < 0) {
            return false;
        }

        const toLeftKey = idx + '-' + arr[idx];
        const toRightKey = idx + '+' + arr[idx];
        if (visited.get(toLeftKey) || visited.get(toRightKey)) {
            return false;
        }

        visited.set(toLeftKey, true);
        visited.set(toRightKey, true);
        return jump(idx - arr[idx]) || jump(idx + arr[idx]);
    }

    return jump(start);
}

점프할 위치를 파라미터로 받는 재귀함수를 만들고,
오른쪽 또는 왼쪽으로 점프를 하도록 재귀를한다.
이미 방문했던 루트면 재귀를 빠져나올 수 있도록 방문했던 위치와 방향을 key 로 여부를 값으로 map 을 생성한다