[Algorithm]

hyena_leeยท2023๋…„ 3์›” 7์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
50/53
post-thumbnail

๐Ÿฆ• treeBFS

๐Ÿ€ ๋ฌธ์ œ ํ’€์ด


let bfs = function (node) {
  let queue = [node];
  const values = [];
  while (queue.length > 0) {
    const head = queue[0];
    queue = queue.slice(1);
    values.push(head.value);
    head.children.forEach((child) => queue.push(child));
  }
  return values;
};

// ์ด ์•„๋ž˜ ์ฝ”๋“œ๋Š” ๋ณ€๊ฒฝํ•˜์ง€ ์•Š์•„๋„ ๋ฉ๋‹ˆ๋‹ค. ์ž์œ ๋กญ๊ฒŒ ์ฐธ๊ณ ํ•˜์„ธ์š”.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// ์œ„ Node ๊ฐ์ฒด๋กœ ๊ตฌ์„ฑ๋˜๋Š” ํŠธ๋ฆฌ๋Š” ๋งค์šฐ ๋‹จ์ˆœํ•œ ํ˜•ํƒœ์˜ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.
// membership check(์ค‘๋ณต ํ™•์ธ)๋ฅผ ๋”ฐ๋กœ ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

๐ŸŒฒ ํšŒ๊ณ 

๋‚ ์ด ๊ฐˆ์ˆ˜๋ก ์–ด๋ ค์›Œ์ง„ ์•Œ๊ณ ๋ฆฌ์ฆ˜..์ด์ œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฌด์—‡์ธ๊ฐ€์š”? ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฌด์—‡์ธ๊ฐ€์š”? ๋จน๋Š”๊ฑด๊ฐ€์š”? ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๋ฉด์„œ ์ €์ €๋ฒˆ์ฃผ์— ์Šคํ„ฐ๋”” ๋ฆฌ๋”๋ถ„์ด ์ด ์ž๋ฃŒ๊ตฌ์กฐ ์ฐธ๊ณ ํ•˜๋ผ๊ณ  ์ฒจ๋ถ€ํ•ด์ฃผ์‹ ๊ฒŒ ๋– ์˜ฌ๋ž๋‹ค. ์ด๋ฌธ์ œ๋ฅผ ์œ„ํ•œ ๋ฐ‘๊ฑฐ๋ฆ„ ํ•˜๋ผ๊ณ  ์ฃผ์…จ๊ตฌ๋‚˜!! ๋‚œ ๋ฐ”์˜๋‹ค๊ณ  ๋‚˜์ค‘์— ๋ด์•ผํ•˜์ง€ ํ•˜๊ณ  ์ด๋ฌธ์ œ๋ฅผ ํ’€์ง€ ๋ชปํ•˜๊ณ  ๊ฒฐ๊ตญ ๋ ˆํผ๋ฅผ ๋ณด๊ณ  ํ‘ผ ๋‚˜์˜ ์ž์‹ ์—๊ฒŒ ๋ฐ˜์„ฑํ•˜๋Š” ์‹œ๊ฐ„์„ ๊ฐ€์ ธ๋ณธ๋‹ค. ๋งค์ผ ๋ฐ˜์„ฑํ•ด๋„ ๋‹ฌ๋ผ์ง€์ง€ ์•Š๋Š” ๋‚˜๋Š” ์ •๋ง ๋ชป๋‚ฌ๋‹ค... ์ƒ์„ ์ฐจ๋ ค์ค˜๋„ ๋– ๋จน์ง€ ๋ชปํ•œ ์„ธ์ƒ์˜ ๋ฐ”๋ณด๊ฐ€ ์–ด๋”” ์žˆ๋˜๊ฐ€..์—ฌ๊ธฐ...๋ฐ”๋กœ ์—ฌ๊ธฐ...์˜ค๋Š˜ ๋˜ ๋ฐ˜์„ฑ์˜ ์‹œ๊ฐ„์„ ๊ฐ–๊ณ  ๋ฆฌ๋”๋ถ„์ด ์ฃผ์‹  ์ž๋ฃŒ ๊ตฌ์กฐ ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

โญ๏ธ ์ •๋ฆฌํ•˜๊ธฐ

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ํƒ์ƒ‰ ํ•„์š”ํ•˜๋‹ค.
DFS์™€ BFS ๋Š” ๋Œ€ํ‘œ์ ์ธ ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค
์ฐธ์กฐ ๋งํฌ

profile
์‹ค์ˆ˜๋ฅผ ๋‘๋ ค์›Œ ๋ง๊ณ  ๊ณ„์† ๋„์ „ ํ•˜๋Š” ๊ฐœ๋ฐœ์ž์˜ ์—ฌ์ •!

0๊ฐœ์˜ ๋Œ“๊ธ€

Powered by GraphCDN, the GraphQL CDN