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
๋ ๋ํ์ ์ธ ๊ทธ๋ํ ํ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ค
์ฐธ์กฐ ๋งํฌ