[백준/JS] 5014 스타트링크

문제

✏️ 문제풀이

최소 경로를 구하는 문제이기 때문에 BFS를 사용해주면 됩니다.

1. 층수를 저장할 1차원 배열
2. U,D 위 아래로 두 가지 형태의 이동

이 두가지만 잘 기억하면 됩니다!

const filePath = process.platform === 'linux' ? '/dev/stdin' : './test.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const [F, S, G, U, D] = input.shift().split(' ').map(Number);

let visited = Array(F + 1).fill(false);
visited[0] = true;

function bfs() {
    let queue = [[S, 0]];
    visited[S] = true;

    while (queue.length) {
        let [x, cnt] = queue.shift();

        if (x + U <= F && x + U >= 1 && !visited[x + U]) {
            if (x + U === G) return console.log(cnt + 1);

            queue.push([x + U, cnt + 1]);
            visited[x + U] = true;
        }
        if (x - D <= F && x - D >= 1 && !visited[x - D]) {
            if (x - D === G) return console.log(cnt + 1);

            queue.push([x - D, cnt + 1]);
            visited[x - D] = true;
        }
    }

    return console.log('use the stairs');
}

bfs();

처음엔 코드를 이와 같이 짰습니다. 그랬더니 바로 틀렸습니다!가 떴습니다!!
그래서 visited를 하나씩 찍어봤습니다.

//  1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0
//  1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0
//  1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0
//  1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0
//  1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0
//  1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0
//  1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0
//  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0

보면 마지막까지 탐색을 안하는 것을 확인할 수 있습니다. (1이 true 0이 false)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './test.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const [F, S, G, U, D] = input.shift().split(' ').map(Number);

let visited = Array(F + 1).fill(false);
visited[0] = true;

function bfs() {
    let queue = [[S, 0]];
    visited[S] = true;

    while (queue.length) {
        let [x, cnt] = queue.shift();

        if (x === G) return cnt;

        if (x + U <= F && x + U > 0 && !visited[x + U]) {
            queue.push([x + U, cnt + 1]);
            visited[x + U] = true;
        }
        if (x - D <= F && x - D > 0 && !visited[x - D]) {
            queue.push([x - D, cnt + 1]);
            visited[x - D] = true;
        }
    }

    return 'use the stairs';
}

console.log(bfs());

위와 같이 코드를 변경해주었습니다.

//  1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0
//  1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0
//  1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0
//  1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0
//  1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0
//  1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0
//  1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0
//  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0
//  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

이러면 끝까지 완전탐색을 하는 것을 확인할 수 있습니다.

제 전 코드는 방향을 탐색함과 동시에 다음 이동칸이 최종목적지인지 확인을 함과 동시에 반환을 해버립니다. 그래서 완전히 탐색을 진행하지 않고 결과값을 반환해버리는 것입니다.

이럴경우 마지막까지 이동을 해봐야 하는 경우에 대해서 오류가 발생하게 될 것 입니다.
그래서 해당 층수를 확인할 때는 큐에 담긴 현재 위치를 가져왔을 때 그때 확인해보면 됩니다.

✏️ 결과코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './test.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

const [F, S, G, U, D] = input.shift().split(' ').map(Number);

let visited = Array(F + 1).fill(0);
visited[0] = 1;

function bfs() {
    let queue = [[S, 0]];
    visited[S] = 1;

    while (queue.length) {
        let [x, cnt] = queue.shift();

        if (x === G) return cnt;

        if (x + U <= F && x + U > 0 && !visited[x + U]) {
            queue.push([x + U, cnt + 1]);
            visited[x + U] = 1;
            console.log(visited);
        }
        if (x - D <= F && x - D > 0 && !visited[x - D]) {
            queue.push([x - D, cnt + 1]);
            visited[x - D] = 1;
            console.log(visited);
        }
    }

    return 'use the stairs';
}

console.log(bfs());