๋ฌธ์ ๋งํฌ
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 |