๋ฐฑ์ค€[node.js] > 14940๋ฒˆ ์‰ฌ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ

2024. 12. 30. 21:38ยท๐Ÿ”’Algorithm

๋ฌธ์ œ๋งํฌ

https://www.acmicpc.net/problem/14940

 

๋ฌธ์ œํ’€์ด

๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰์œผ๋กœ ์‹œ์ž‘์ ์œผ๋กœ ๋ถ€ํ„ฐ ๋™์„œ๋‚จ๋ถ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์‹ ํ•˜์˜€๋‹ค. 

๋ฌด๋ฆฌ์—†์ด ํ’€ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

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

let [N, M] = input
    .shift()
    .split(" ")
    .map((n) => Number(n));

let s_row = undefined,
    s_column = undefined;

let map = [];
for (let i = 0; i < input.length; ++i) {
    let line = input[i].split(" ").map((n) => Number(n));

    line.forEach((v, column) => {
        if (v === 2) {
            s_row = i;
            s_column = column;
        }
    });
    map.push(line);
}

let answer = Array.from({ length: N }, () => {
    return Array(M).fill(Infinity);
});

answer[s_row][s_column] = 0;

let nextPoint = [[s_row, s_column]];

// ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰
while (nextPoint.length) {
    let [now_r, now_c] = nextPoint.shift();
    let now_distance = answer[now_r][now_c];

    // ๋™์„œ๋‚จ๋ถ
    let dr = [0, 0, 1, -1];
    let dc = [1, -1, 0, 0];

    for (let i = 0; i < 4; ++i) {
        let nextRow = now_r + dr[i];
        let nextColumn = now_c + dc[i];

        if (map[nextRow] && map[nextRow][nextColumn] === 1 && now_distance + 1 < answer[nextRow][nextColumn]) {
            answer[nextRow][nextColumn] = now_distance + 1;
            nextPoint.push([nextRow, nextColumn]);
        }
    }
}

// ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์‹ ํ•˜์ง€ ๋ชปํ•œ ๊ณณ์„ ์• ์ดˆ์— ๋„๋‹ฌํ• ์ˆ˜ ์—†๋Š” ๊ณณ(0)๊ณผ ๊ฐˆ์ˆ˜์žˆ๋Š” ๊ณณ(1)๋กœ ๊ตฌ๋ถ„ํ•˜์—ฌ 
// ๊ฐˆ์ˆ˜ ์žˆ๋Š” ๊ณณ์€ -1 ๊ฐ€์ง€ ๋ชปํ•˜๋Š” ๊ณณ์€ 0 ์œผ๋กœ ์น˜ํ™˜
answer.forEach((line, row) => {
    line.forEach((distance, column) => {
        if (distance === Infinity) {
            if (map[row][column] === 0) {
                answer[row][column] = 0;
            } else if (map[row][column] === 1) {
                answer[row][column] = -1;
            }
        }
    });
});

let str = "";
answer.forEach((row) => {
    str = str + row.join(" ") + "\n";
});

console.log(str.trim());

 

'๐Ÿ”’Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

๋ฐฑ์ค€[node.js] > 11399๋ฒˆ ATM  (0) 2025.01.02
๋ฐฑ์ค€[node.js] > 11279๋ฒˆ ์ตœ๋Œ€ ํž™  (0) 2024.12.31
๋ฐฑ์ค€[node.js] > 10026๋ฒˆ ์ ๋ก์ƒ‰์•ฝ  (0) 2024.12.28
๋ฐฑ์ค€[node.js] > 2667๋ฒˆ ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ  (2) 2024.12.22
๋ฐฑ์ค€[node.js] > 2805๋ฒˆ ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ  (1) 2024.12.21
'๐Ÿ”’Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ๋ฐฑ์ค€[node.js] > 11399๋ฒˆ ATM
  • ๋ฐฑ์ค€[node.js] > 11279๋ฒˆ ์ตœ๋Œ€ ํž™
  • ๋ฐฑ์ค€[node.js] > 10026๋ฒˆ ์ ๋ก์ƒ‰์•ฝ
  • ๋ฐฑ์ค€[node.js] > 2667๋ฒˆ ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ
devWarrior
devWarrior
  • devWarrior
    devWarrior
    devWarrior
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๐ŸงฉDev (263)
      • โญFE (34)
      • ๐Ÿ”’Algorithm (155)
      • โž•Etc. (11)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
    • ๊ธ€์“ฐ๊ธฐ
    • ๊ด€๋ฆฌ
  • ๋งํฌ

  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    BFS
    ์ž์Šค
    ๋ฐฑ์ค€
    react
    Easy
    ๊ตฌํ˜„
    ์‹ค๋ฒ„3
    ๊ทธ๋ฆฌ๋””
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    nodejs
    DFS
    ์˜ค๋ธ”์™„
    ์ฝ”ํ…Œ
    ์‹ค๋ฒ„2
    ์‹ค๋ฒ„1
    Lv2
    Algorithm
    ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
    dp
    ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ
    ๊ณจ๋“œ5
    leetcode
    node.js
    FE
    ์•Œ๊ณ ๋ฆฌ์ฆ˜
    js
    ์‹ค๋ฒ„4
    ํ”„๋ก ํŠธ์—”๋“œ
    ํ‹ฐ์Šคํ† ๋ฆฌ์ฑŒ๋ฆฐ์ง€
    javascript
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
devWarrior
๋ฐฑ์ค€[node.js] > 14940๋ฒˆ ์‰ฌ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”