๐Ÿ… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 120866 : ์•ˆ์ „์ง€๋Œ€ - Javascript

๋ฌธ์ œ ์„ค๋ช…

๋‹ค์Œ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ง€๋ขฐ๊ฐ€ ์žˆ๋Š” ์ง€์—ญ๊ณผ ์ง€๋ขฐ์— ์ธ์ ‘ํ•œ ์œ„, ์•„๋ž˜, ์ขŒ, ์šฐ ๋Œ€๊ฐ์„  ์นธ์„ ๋ชจ๋‘ ์œ„ํ—˜์ง€์—ญ์œผ๋กœ ๋ถ„๋ฅ˜ํ•ฉ๋‹ˆ๋‹ค.

description.png

์ง€๋ขฐ๋Š” 2์ฐจ์› ๋ฐฐ์—ด board์— 1๋กœ ํ‘œ์‹œ๋˜์–ด ์žˆ๊ณ  board์—๋Š” ์ง€๋ขฐ๊ฐ€ ๋งค์„ค ๋œ ์ง€์—ญ 1๊ณผ, ์ง€๋ขฐ๊ฐ€ ์—†๋Š” ์ง€์—ญ 0๋งŒ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.

์ง€๋ขฐ๊ฐ€ ๋งค์„ค๋œ ์ง€์—ญ์˜ ์ง€๋„ board๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์•ˆ์ „ํ•œ ์ง€์—ญ์˜ ์นธ ์ˆ˜๋ฅผ returnํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


์ œํ•œ์‚ฌํ•ญ

  • board๋Š” nโˆ—nn * n ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.
  • 1 โ‰ค n โ‰ค 100
  • ์ง€๋ขฐ๋Š” 1๋กœ ํ‘œ์‹œ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • board์—๋Š” ์ง€๋ขฐ๊ฐ€ ์žˆ๋Š” ์ง€์—ญ 1๊ณผ ์ง€๋ขฐ๊ฐ€ ์—†๋Š” ์ง€์—ญ 0๋งŒ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

board result
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]] 16
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0]] 13
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] 0
  • ์˜ˆ์ œ #1
    (3, 2)์— ์ง€๋ขฐ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ ์ง€๋ขฐ๊ฐ€ ์žˆ๋Š” ์ง€์—ญ๊ณผ ์ง€๋ขฐ์™€ ์ธ์ ‘ํ•œ ์œ„, ์•„๋ž˜, ์ขŒ, ์šฐ, ๋Œ€๊ฐ์„  ์ด 8์นธ์€ ์œ„ํ—˜์ง€์—ญ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ 16์„ returnํ•ฉ๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2
    (3, 2), (3, 3)์— ์ง€๋ขฐ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ ์ง€๋ขฐ๊ฐ€ ์žˆ๋Š” ์ง€์—ญ๊ณผ ์ง€๋ขฐ์™€ ์ธ์ ‘ํ•œ ์œ„, ์•„๋ž˜, ์ขŒ, ์šฐ, ๋Œ€๊ฐ์„ ์€ ์œ„ํ—˜์ง€์—ญ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์œ„ํ—˜์ง€์—ญ์„ ์ œ์™ธํ•œ ์นธ ์ˆ˜ 13์„ returnํ•ฉ๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2
    ๋ชจ๋“  ์ง€์—ญ์— ์ง€๋ขฐ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ ์•ˆ์ „์ง€์—ญ์€ ์—†์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ 0์„ returnํ•ฉ๋‹ˆ๋‹ค.


ํ’€์ด ๊ณผ์ •

๋จผ์ € ์ฃผ์–ด์ง„ 2์ฐจ์› ๋ฐฐ์—ด์—์„œ ์ง€๋ขฐ๊ฐ€ ๋งค์„ค ๋œ ์ง€์—ญ ์ฃผ๋ณ€์„ ์•ˆ์ „ํ•œ ์ง€์—ญ์„ ์œ„ํ—˜์ง€์—ญ์œผ๋กœ ๋ฐ”๊ฟ‰๋‹ˆ๋‹ค.

  • ์•ˆ์ „ํ•œ ์ง€์—ญ์€ 0, ์ง€๋ขฐ๊ฐ€ ๋งค์„ค ๋œ ์ง€์—ญ์€ 1๋กœ ํ‘œํ˜„๋˜๊ธฐ ๋•Œ๋ฌธ์— ์œ„ํ—˜์ง€์—ญ์„ 2๋กœ ํ‘œํ˜„ํ–ˆ์Šต๋‹ˆ๋‹ค.

๊ทธ ํ›„ ๋‚จ์€ ์•ˆ์ „์ง€์—ญ์˜ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

const SAFE = 0; //์•ˆ์ „ํ•œ ์ง€์—ญ
const BOOM = 1; //์ง€๋ขฐ๊ฐ€ ๋งค์„ค ๋œ ์ง€์—ญ
const WARN = 2; //์œ„ํ—˜์ง€์—ญ

function solution(board) {
  //board๋Š” n*n์˜ ๋ฐฐ์—ด์ด๊ธฐ ๋•Œ๋ฌธ์— n์„ ๊ตฌํ•จ
  const n = board.length;

  //์ฃผ์–ด์ง„ ์ง€์—ญ๊ณผ ์ธ์ ‘ํ•œ ์•ˆ์ „ํ•œ ์ง€์—ญ์„ ์œ„ํ—˜์ง€์—ญ์œผ๋กœ ๋ณ€๊ฒฝํ•˜๋Š” ํ•จ์ˆ˜
  const markWarn = (x, y) => {
    //board๋ฅผ ๋ฒ—์–ด๋‚˜์ง€ ์•Š๋Š” ํƒ์ƒ‰ ๋ฒ”์œ„๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
    const range = (k) => [Math.max(0, k - 1), k, Math.min(n - 1, k + 1)];

    //์ฃผ์–ด์ง„ x, y๋กœ ๊ตฌํ•œ ๋ฒ”์œ„ ๋‚ด์˜ ์•ˆ์ „ํ•œ ์ง€์—ญ์„ ์œ„ํ—˜ ์ง€์—ญ์œผ๋กœ ๋ณ€๊ฒฝ
    for (const ry of range(y)) {
      for (const rx of range(x)) {
        if (board[ry][rx] === SAFE) {
          board[ry][rx] = WARN;
        }
      }
    }
  };

  //๋ชจ๋“  ์š”์†Œ๋ฅผ ์ˆœํšŒํ•˜์—ฌ ์œ„ํ—˜์ง€์—ญ์„ ํ‘œ์‹œ
  for (let y = 0; y < n; ++y) {
    for (let x = 0; x < n; ++x) {
      if (board[y][x] === BOOM) {
        markWarn(x, y);
      }
    }
  }

  //๋ณด๋“œ๋ฅผ 1์ฐจ์› ๋ฐฐ์—ด๋กœ ๋ฐ”๊พธ๊ณ , ์•ˆ์ „ํ•œ ์ง€์—ญ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด ๋ฐ˜ํ™˜
  return board.flat().filter((el) => el === SAFE).length;
}

๊ฐœ์„ 

๊ธฐ์กด ๋ฐฉ์‹๊ณผ ์ •๋ฐ˜๋Œ€๋กœ, ํ™•์ธํ•  ์ง€์—ญ๊ณผ ์ธ์ ‘ ์ง€์—ญ์— ์ง€๋ขฐ๊ฐ€ ๋งค์„ค๋œ ์ง€์—ญ์ด ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•ด ์•ˆ์ „ํ•œ ์ง€์—ญ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ณ€๊ฒฝํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ ํ†ตํ•ด ์ฝ”๋“œ๋ฅผ ๋” ์ง๊ด€์ ์œผ๋กœ ๊ฐœ์„ ํ•  ์ˆ˜ ์žˆ์—ˆ๊ณ , ๋ถˆํ•„์š”ํ•˜๊ฒŒ ๋งŽ์€ ๋ฐฐ์—ด ์ˆ˜์ • ๋ฐ ์ ‘๊ทผ ํšŸ์ˆ˜๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

function solution(board) {
  //board๋Š” n*n์˜ ๋ฐฐ์—ด์ด๊ธฐ ๋•Œ๋ฌธ์— n์„ ๊ตฌํ•จ
  const n = board.length;

  //์ฃผ์–ด์ง„ ์ง€์—ญ์ด ์•ˆ์ „ํ•œ ์ง€์—ญ์ธ์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
  const isSafe = (x, y) => {
    const range = (k) => [k - 1, k, k + 1];

    //๋ฒ”์œ„ ๋‚ด์— ์ง€๋ขฐ๊ฐ€ ๋งค์„ค๋œ ์ง€์—ญ์ด ์กด์žฌํ•˜๋ฉด false๋ฅผ ๋ฐ˜ํ™˜
    for (const ry of range(y)) {
      for (const rx of range(x)) {
        if (board[ry]?.[rx]) {
          return false;
        }
      }
    }

    //์ฃผ๋ณ€ ์ง€์—ญ์ด ๋ชจ๋‘ ๋นˆ ์ง€์—ญ์ด๋ฉด true๋ฅผ ๋ฐ˜ํ™˜
    return true;
  };

  //๋ชจ๋“  ์ง€์—ญ์„ ์ˆœํšŒํ•˜์—ฌ ์•ˆ์ „ํ•œ ์ง€์—ญ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด ๋ฐ˜ํ™˜
  let answer = 0;
  for (let y = 0; y < n; ++y) {
    for (let x = 0; x < n; ++x) {
      answer += isSafe(x, y);
    }
  }
  return answer;
}

๋ฌธ์ œ์—์„œ 0์€ ์•ˆ์ „ํ•œ ์ง€์—ญ์ด ์•„๋‹ˆ๋ผ ์ง€๋ขฐ๊ฐ€ ๋งค์„ค๋˜์ง€ ์•Š์€ ์ง€์—ญ์„ ์˜๋ฏธํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด ํ’€์ด๊ฐ€ ๋” ์ž์—ฐ์Šค๋Ÿฌ์šด ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ฒ˜์Œ์— ์™œ ์ €๋ ‡๊ฒŒ ํ’€์—ˆ์ง€..


์ˆ์ฝ”๋”ฉ (CodeGolf)

์กฐ๊ธˆ ๋” ์ฝ”๋“œ๋ฅผ ๊ฐ„๊ฒฐํ•˜๊ฒŒ ๋ฐ”๊พธ์–ด ์•„๋ž˜์™€ ๊ฐ™์ด ์ •๋ฆฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

solution=_=>_.flatMap((r,y)=>r.map((v,x)=>{for(i=-1;i<2;++i)for(j=-1;j<2;++j)if(_[y+i]?.[x+j])return 0;return 1})).filter(v=>v).length