[백준] 15558 점프 게임 (Javascript)

문제

BOJ15558_점프 게임

풀이

문제 요약

우선 문제를 요약해보자면 아래와 같다.

N칸짜리 1차원 배열이 2개가 있고, 각 칸은 위험한 칸(0)과 안전한 칸(1)로 구분된다.

안전한 칸만 밟아서 N에 도착하거나 N을 넘어가면 게임이 클리어 된다.

1초 마다 우리는 아래 세 가지 동작 중 하나를 고를 수 있다.

1. i+1칸으로 이동
2. i-1칸으로 이동
3. 반댓줄 i+k 칸으로 이동

또한 유저가 이동하고 난 뒤에는 각 배열의 첫 칸이 사라진다.

유저가 게임을 클리어할 수 있다면 1을 출력하고, 아니라면 0을 출력한다.

접근법

우선 N이 10만이기 때문에 시간복잡도가 $O(N\log N)$ 보다 크면 시간초과가 난다.

따라서 완전 탐색은 탈락이다.

이 문제는 BFS를 통해서 1초마다 현재줄[i+1], 현재줄[i-1], 반대줄[i+k]를 탐색해서, 아직 방문하지 않은 칸이 있다면 해당 칸을 큐에 삽입하고 방문처리 해줌으로써 풀 수 있다.

이렇게 하면 이미 방문한 칸을 재방문하지 않아도 되고, 따라서 모든 칸을 한 번씩만 방문해주면 되기 때문에 $O(N)$의 시간복잡도로 풀 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const line = input.slice(1).map((e) => e.trimEnd().split('').map(Number));

// line[0] = 왼쪽,  line[1] = 오른쪽

// 현재줄[i+1]===1이고, 방문하지 않았고, i+1 >= time+1 이라면 [현재줄, i+1, tiem+1]을 큐에 삽입한다.
// 현재줄[i-1]===1이고, 방문하지 않았고, i-1 >= time+1 이라면 [현재줄, i-1, tiem+1]을 큐에 삽입한다.
// 반대줄[i+k]===1이고, 방문하지 않았고, i+k >= time+1 이라면 [반대줄, i+k, item+1]큐에 삽입한다.

// i >= N 이라면 실행을 마치고 1을 출력한다.
// 큐가 비었는데 끝나지 않았다면 0을 출력한다.
// N번째 칸을 넘어가도 클리어 처리되도록 한다. 

// * 방문한 칸은 0으로 만들어서 방문처리 한다.


console.log(bfs([0, 0, 0]));

function bfs(start) {
    const queue = [start];
    let front = 0;
    while (queue.length > front) {
        const [curLine, i, time] = queue[front++];
        const acrossLine = curLine ? 0 : 1;
        if (i >= N - 1) return 1;
        if (line[curLine][i + 1] === 1 || i + 1 > N - 1) {
            line[curLine][i + 1] = 0;
            queue.push([curLine, i + 1, time + 1]);
        }
        if (line[curLine][i - 1] === 1) {
            line[curLine][i - 1] = 0;
            queue.push([curLine, i - 1, time + 1]);
        }
        if (line[acrossLine][i + K] === 1 || i + K > N - 1) {
            line[acrossLine][i + K] = 0;
            queue.push([acrossLine, i + K, time + 1]);
        }
        line[curLine][time] = 0;
        line[acrossLine][time] = 0;
    }
    return 0;
}