[백준] 16928_뱀과 사다리 게임 (Javascript)

문제

BOJ16928_뱀과 사다리 게임

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const ladder = input.slice(1, N + 1).map((e) => e.split(' ').map(Number));
const snake = input.slice(N + 1).map((e) => e.split(' ').map(Number));
const visited = Array(101).fill(false);
const arr = Array(101).fill(0);

// 사다리
for (let [x, y] of ladder) {
    arr[x] = y;
}
// 뱀
for (let [u, v] of snake) {
    arr[u] = v;
}

let answer = bfs(1, 0);
console.log(answer);

function bfs(start, count) {
    const queue = [[start, count]];
    let front = 0;
    visited[start] = true;
    while (queue.length > front) {
        const [v, diceCount] = queue[front++];
        for (let i = 1; i <= 6; i++) {
            let next = v + i;
            if (next === 100) return diceCount + 1;
            else if (next < 100) {
                // 사다리 혹은 뱀일 경우 해당 위치로 이동 (카운트는 증가하지 않음)
                if (arr[next] !== 0) {
                    next = arr[next];
                }
                if (!visited[next]) {
                    queue.push([next, diceCount + 1]);
                    visited[next] = true;
                }
            }
        }
    }
}

풀이

BFS를 통해 풀 수 있는 문제다.

우선 사다리와 뱀이 있는 위치를 arr 변수에 저장해주고, BFS를 수행한다.

큐에는 현재 위치(v)와 주사위를 굴린 횟수(diceCount)가 저장되고, 큐에서 원소를 하나 꺼낼때마다 반복문을 1~6까지(주사위 눈금의 개수) 반복해주며 현재 지점(v)에 눈금의 개수(i)를 더하여 다음 지점(next)을 계산해준다.

만약 next가 100이라면 목표 지점에 도착한 것이므로 distance에 1을 더한 값을 반환하며 함수를 종료한다.

그렇지 않고 만약 next가 100보다 작다면 아직 목표 지점까지 도달하지 못한 것이므로 이동을 수행해주어야 한다.

현재 위치가 사다리나 뱀이 있는 위치라면 연결된 위치로 이동한다. (사다리나 뱀을 타고 이동하는 것은 주사위를 굴려 이동한 것이 아니므로 카운트를 증가시키지 않는다.)

그런 다음 방문 여부를 확인하고 다음 지점(next)과 주사위 굴린 횟수(diceCount)에 1을 증가시킨 값을 큐에 넣어주고 방문처리 해준다.

최단 거리를 찾는 것이기 때문에 방문해준 곳을 또다시 방문해줄 필요가 없으므로 이미 방문한 곳은 방문처리 해주어 중복되는 연산을 제거함으로써 동작 시간을 줄일 수 있다.

참고

https://hagisilecoding.tistory.com/85