πŸ… ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 120866 : μ•ˆμ „μ§€λŒ€ - Javascript

μ•Œκ³ λ¦¬μ¦˜ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€

문제 μ„€λͺ…

λ‹€μŒ κ·Έλ¦Όκ³Ό 같이 지뒰가 μžˆλŠ” 지역과 지뒰에 μΈμ ‘ν•œ μœ„, μ•„λž˜, 쒌, 우 λŒ€κ°μ„  칸을 λͺ¨λ‘ μœ„ν—˜μ§€μ—­μœΌλ‘œ λΆ„λ₯˜ν•©λ‹ˆλ‹€.

description.png

μ§€λ’°λŠ” 2차원 λ°°μ—΄ board에 1둜 ν‘œμ‹œλ˜μ–΄ 있고 boardμ—λŠ” 지뒰가 맀섀 된 지역 1κ³Ό, 지뒰가 μ—†λŠ” 지역 0만 μ‘΄μž¬ν•©λ‹ˆλ‹€.

지뒰가 λ§€μ„€λœ μ§€μ—­μ˜ 지도 boardκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, μ•ˆμ „ν•œ μ§€μ—­μ˜ μΉΈ 수λ₯Ό returnν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”.


μ œν•œμ‚¬ν•­

  • boardλŠ” nβˆ—nn * n λ°°μ—΄μž…λ‹ˆλ‹€.
  • 1 ≀ n ≀ 100
  • μ§€λ’°λŠ” 1둜 ν‘œμ‹œλ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€.
  • boardμ—λŠ” 지뒰가 μžˆλŠ” 지역 1κ³Ό 지뒰가 μ—†λŠ” 지역 0만 μ‘΄μž¬ν•©λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

boardresult
[[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