백준 14248 JS 풀이

구하는 값

범위 내에서 자리 값만큼 점프하며 방문할 수 있는 자리 수

핵심 아이디어

dfs, bfs로 탐색함

3가지 방식으로 풀어봤음

BFS-array 코드

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
const graph = [0, ...input[1].split(" ").map(Number)];
const str = Number(input[2]);
const visited = new Array(n + 1).fill(false);

// bfs 풀이 - array
const que = [];
que.push(str);
visited[str] = true;

while (que.length) {
    const cur = que.shift();

    for (const d of [-1, 1]) {
        const next = cur + d * graph[cur];

        if (next <= 0 || next > n) continue;
        if (!visited[next]) {
            que.push(next);
            visited[next] = true;
        }
    }
}
console.log(visited.filter((v) => v).length);

BFS-que 코드

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
const graph = [0, ...input[1].split(" ").map(Number)];
const str = Number(input[2]);
const visited = new Array(n + 1).fill(false);

// bfs 풀이 - que
class Que {
    q = [];
    h = 0;
    t = 0;
    push(v) {
        this.q[this.t++] = v;
    }
    shift() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    length() {
        return this.t - this.h;
    }
}
const que = new Que();
que.push(str);
visited[str] = true;

while (que.length()) {
    const cur = que.shift();

    for (const d of [-1, 1]) {
        const next = cur + d * graph[cur];

        if (next <= 0 || next > n) continue;
        if (!visited[next]) {
            que.push(next);
            visited[next] = true;
        }
    }
}
console.log(visited.filter((v) => v).length);

DFS 코드

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const n = Number(input[0]);
const graph = [0, ...input[1].split(" ").map(Number)];
const str = Number(input[2]);
const visited = new Array(n + 1).fill(false);

// dfs 풀이
const dfs = (cur) => {
    visited[cur] = true;

    for (const d of [-1, 1]) {
        const next = cur + d * graph[cur];

        if (next <= 0 || next > n) continue;
        if (!visited[next]) dfs(next);
    }
};
dfs(str);
console.log(visited.filter((v) => v).length);