๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/LeetCode

[LeetCode] binary Tree Cameras

๋ฌธ์ œ๋งํฌ

 

Binary Tree Cameras - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

binary tree๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.
tree ๊ตฌ์กฐ์—์„œ ์ž„์˜์˜ ๋…ธ๋“œ์— ์นด๋ฉ”๋ผ๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ๋‹ค๋ฉด ๊ทธ ๋…ธ๋“œ์˜ ์ง๊ณ„ ๋ถ€๋ชจ, ์ง๊ณ„ ์ž์†์„ ๋ชจ๋‘ ๋ชจ๋‹ˆํ„ฐ๋งํ•  ์ˆ˜ ์žˆ๋‹ค.
์ด๋•Œ ํŠธ๋ฆฌ์—์„œ ๊ฐ€์žฅ ์ ๊ฒŒ ์นด๋ฉ”๋ผ๋ฅผ ์„ค์น˜ํ•˜๋Š” ๊ฒฝ์šฐ ์นด๋ฉ”๋ผ๋Š” ๋ช‡๋Œ€๊ฐ€ ํ•„์š”ํ•œ์ง€ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

DFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ†ตํ•ด ๊ฐ€์žฅ ๊นŠ์€ ๋…ธ๋“œ(์ตœํ•˜๋‹จ leaf node)๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ•œ๋‹ค.

dfs๋ฅผ ์ง„ํ–‰ํ•˜๋ฉฐ ๊ฐ€์ •ํ•  ์ˆ˜ ์žˆ๋Š” ์ƒํ™ฉ์€ 4๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.
(covered : ์นด๋ฉ”๋ผ๋กœ ๋ชจ๋‹ˆํ„ฐ๋ง ๋˜๋Š” ์ƒํƒœ,  notCovered : ๋ชจ๋‹ˆํ„ฐ๋ง๋˜์ง€ ์•Š๋Š” ์ƒํƒœ, hasCamera : ์นด๋ฉ”๋ผ๋ฅผ ๊ฐ–๋Š” ๋…ธ๋“œ)
1. ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง€๋Š” ์ตœํ•˜๋‹จ node๊ฐ€ falsy(null)์ผ๋•Œ, covered ์ƒํƒœ๋ฅผ ๋ฐ˜ํ™˜
2. ๋‘ ์ž์‹๋…ธ๋“œ(left, right)๊ฐ€ covered์ผ๋•Œ notCovered ์ƒํƒœ๋ฅผ ๋ฐ˜ํ™˜
    (๊นŠ์ด ์šฐ์„ ์ด๋ฏ€๋กœ ์ž์‹์ด hasCamera๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด notCovered์ผ ์ˆ˜ ๋ฐ–์— ์—†๋‹ค.)
3. ๋‘ ์ž์‹๋…ธ๋“œ ์ค‘ ํ•˜๋‚˜๋ผ๋„ notCovered๋ผ๋ฉด hasCamera ์ƒํƒœ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ์นด๋ฉ”๋ผ ๊ฐœ์ˆ˜ + 1
    ( ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ covered๋˜๋Š” hasCamera์—ฌ์•ผ ํ•˜๋ฏ€๋กœ )
4. ๋‘ ์ž์‹๋…ธ๋“œ ์ค‘ ํ•˜๋‚˜๋ผ๋„ hasCamera๋ผ๋ฉด Covered์ƒํƒœ๋ฅผ ๋ฐ˜ํ™˜
    (์ง๊ณ„ ์ž์†์ด camera๊ฐ€ ์žˆ๋‹ค๋ฉด ๋ถ€๋ชจ๋„ ๋ชจ๋‹ˆํ„ฐ๋ง ํ•  ์ˆ˜ ์žˆ๋‹ค.)

์ด์ฒ˜๋Ÿผ dfs๋ฅผ ํ†ตํ•ด ๊นŠ์ด ์šฐ์„  ์ˆœ์ฐจํƒ์ƒ‰ ๋ฐฉ์‹์œผ๋กœ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•  ์ˆ˜ ์žˆ๋‹ค.
(์ฐธ๊ณ ํ•œ ๋ธ”๋กœ๊ทธ)

 

var minCameraCover = function (root) {
  let count = 0;
  const notCovered = 0;
  const hasCamera = 1;
  const covered = 2;

  function dfs(root) {
    // Recursive termination condition
    if (!root) {
      return covered;
    }

    const left = dfs(root.left);
    const right = dfs(root.right);
    if (left === covered && right === covered) {
      return notCovered;
    } else if (left === notCovered || right === notCovered) {
      count++;
      return hasCamera;
    } else if (left === hasCamera || right === hasCamera) {
      return covered;
    }
  }
  if (dfs(root) === notCovered) {
    count++;
  }

  return count;
};

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

'์ฝ”๋”ฉํ…Œ์ŠคํŠธ > LeetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[LeetCode] 3Sum  (0) 2022.06.23
[LeetCode] Furthest Building You Can Reach  (0) 2022.06.21
[LeetCode] search-suggestions-system  (0) 2022.06.19
[LeetCode] Zigzag Conversion  (0) 2022.06.17
[LeetCode] Longest Substring without Repeating Characters  (0) 2022.06.17