[백준] 4485_녹색 옷 입은 애가 젤다지? (Javascript)

문제

BOJ4485_녹색 옷 입은 애가 젤다지?

풀이

네 방향을 확인하며 모든 지점을 순회한다. 이때, 다익스트라 처럼 최단 거리 테이블을 사용하는데, 최단거리를 갱신할 수 있다면 갱신하고 해당 위치(좌표)를 큐에 넣어 BFS를 수행하면 된다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let N = +input.shift();
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
let answerCount = 1;
let answer = '';

while (N !== 0) {
    const map = input.splice(0, N).map((e) => e.split(' ').map(Number));
    dijkstra([0, 0], map);
    N = +input.shift();
}

console.log(answer.trimEnd());

function dijkstra(start, map) {
    const [x, y] = start;
    const distance = Array.from({ length: N }, () => Array(N).fill(Infinity));

    // 다익스트라 + BFS
    const queue = [[x, y]];
    let front = 0;
    distance[y][x] = map[y][x];

    while (queue.length > front) {
        const [x, y] = queue[front++];
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (ny >= 0 && nx >= 0 && ny < N && nx < N && distance[ny][nx] > distance[y][x] + map[ny][nx]) {
                distance[ny][nx] = distance[y][x] + map[ny][nx];
                queue.push([nx, ny]);
            }
        }
    }
    answer += `Problem ${answerCount++}: ${distance[N - 1][N - 1]}\n`;
}