ํฐ์คํ ๋ฆฌ ๋ทฐ
๋ฌธ์
์์ฐ์ N์ด ์ฃผ์ด์ง๋ฉด 1๋ถํฐ N๊ฐ๊น์ง์ ์์๋ฅผ ๊ฐ๋ ์งํฉ์ ๋ถ๋ถ์งํฉ์ ๋ชจ๋ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ธ์.
๋ฌธ์ ํ์ด
- ์์๊ฐ ํฌํจ๋๋(1) ํฌํจ๋์ง ์๋๋(0)์ ๋ฐ๋ผ ๋ ๊ฐ์ ์ผ๋ก ๋๋
- ์์ฐ์ N๊ฐ๊น์ง ํ์์ ๊ณ์ ํ๊ณ N์ ๋ฒ์๋ฅผ ๋์ด์๊ฒ ๋๋ฉด ํ์์ ์ข ๋ฃ ๋ฐ ๋ถ๋ถ์งํฉ ์ถ๋ ฅ
- ๋ถ๋ถ์งํฉ์ ์ถ๋ ฅํ๊ธฐ ์ํด์ ์ง๊ธ๊น์ง ํ์ ํ๋ ์์๋ค์ด ํฌํจ์ธ์ง ๋ฏธํฌํจ์ธ์ง ์ฒดํฌํด๋ ๋ณ๋์ ๋ณ์ ํ์
์ฝ๋
function solution(n) {
let answer = [];
let check = Array.from({length: n + 1}, () => 0); //ํฌํจ์ธ์ง ๋ฏธํฌํจ์ธ์ง ์ฒดํฌํ๋ ๋ฐฐ์ด(์์ฐ์ 1๋ถํฐ ์์์ด๊ธฐ ๋๋ฌธ์ ์ฒดํฌ ๋ฐฐ์ด ๋ํ 1๊ฐ์ฐ)
function DFS(v) {
if(v === n + 1) { //N์ ๋ฒ์๋ฅผ ๋์ด์ฐ์ ๊ฒฝ์ฐ
let tmp = '';
for(let i = 1; i < check.length; i++) {
if(check[i] === 1) tmp += i + ''; //ํฌํจ(1)์ผ ๊ฒฝ์ฐ์ ์์๋ค๋ง ์ถ๋ ฅ
}
if(tmp.length > 0) answer.push(tmp.trim());
}
else {
check[v] = 1; //ํฌํจ
DFS(v + 1); //์ผ์ชฝ ๊ฐ์ ์ผ๋ก ํ์
check[v] = 0; //๋ฏธํฌํจ
DFS(v + 1); //์ค๋ฅธ์ชฝ ๊ฐ์ ์ผ๋ก ํ์
}
}
DFS(1);
return answer;
}
console.log(solution(3));
'์๊ณ ๋ฆฌ์ฆ > ํ๊ทธ ๋ณ ํ์ด' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[DFS]์ต๋ ์ ์ ๊ตฌํ๊ธฐ (0) | 2021.08.04 |
---|---|
[DFS]ํฉ์ด ๊ฐ์ ๋ถ๋ถ์งํฉ (0) | 2021.07.30 |
[DFS]์ด์งํธ๋ฆฌ ์ํ (0) | 2021.07.28 |
[์ฌ๊ทํจ์์ ์คํ ํ๋ ์]์ด์ง์ ์ถ๋ ฅ (0) | 2021.07.27 |
[๊ฒฐ์ ์๊ณ ๋ฆฌ์ฆ]๋ฎค์ง๋น๋์ค (0) | 2021.07.25 |
๋๊ธ