[ ์๋ฐ์คํฌ๋ฆฝํธ(JavaScript) ] section08 - 10 - ์์ด๊ตฌํ๊ธฐ
๐ section08 - 10 - ์์ด๊ตฌํ๊ธฐ
๋ฌธ์ : 10 ์ดํ์ N
๊ฐ์ ์์ฐ์๊ฐ ์ฃผ์ด์ง๋ฉด ์ด ์ค M
๊ฐ๋ฅผ ๋ฝ์ ์ผ๋ ฌ๋ก ๋์ดํ๋ ๋ฐฉ๋ฒ์ ๋ชจ๋ ์ถ๋ ฅํ๋ผ.(์ค๋ณต์ ํ๋ฝํ์ง ์๋๋ค.)
// ์
๋ ฅ
3 2
3 6 9
// ์ถ๋ ฅ
3 6
3 9
6 3
6 9
9 3
9 6
์ด์ ์ ํ์๋ ์ค๋ณต์ ํ๋ฝํ์ฌ ์์ด ๊ตฌํ๊ธฐ์ ๋น์ทํ ๋ฌธ์ ์ด์ง๋ง ์ด๋ฒ์ ์ค๋ณต์ ํ๋ฝํ์ง ์๋ ์กฐ๊ฑด์์ ํธ๋ ๋ฌธ์ ๋ค. ์ค๋ณต์ ํ๋ฝํ์ง ์์์ ๋ ๋์ฌ ์ ์๋ ์ ์ฒด ๊ฒฝ์ฐ์ ์๋ 3*2=6
์ด๋ค. ํต์ฌ ํฌ์ธํธ๋ visited
๋ฐฐ์ด์ ์ ์ธํ์ฌ ์ด์ ์ ๋ฐฉ๋ฌธํ๋ index
๋ ์ ์ธํ๊ณ ๋ฐฉ๋ฌธํ๋ฉด ์ค๋ณต๋์ง ์์ ๊ฐ์ด ๋์จ๋ค. ๋ํ, ๋ฐฉ๋ฌธํ๊ณ ๋ค์ ์ฌ๋ผ๊ฐ ๋ visited
๋ฅผ 0์ผ๋ก ๋ฐ๊ฟ์ค์ผ ๋ค์ L
์์ index
๋ฅผ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ค๋ ์ ์ด๋ค. visited
๋ฅผ 0์ผ๋ก ๋ฐ๊ฟ์ฃผ์ง ์์ผ๋ฉด ์ถ๋ ฅ์ด [3, 6], [3, 9]
์ผ๋ก๋ง ๋์จ๋ค. ๋ง์ง๋ง์ ์ถ๋ ฅํ ๋๋ answer
์ ์์๋ณต์ฌslice
๋ก push
ํ๋ค.
let n = 3;
let m = 2;
let arr = [3, 6, 9];
console.log(solution(n, m, arr));
function solution(n, m, arr){
let temp = Array.from({length: m}, ()=>0);
let visited = Array.from({length: n}, ()=>0);
let answer = [];
function DFS(L){
if (L === m){
answer.push(temp.slice());
}else{
for (let i=0; i<n; i++){
if (!visited[i]){
visited[i] = 1 // ๋ฐฉ๋ฌธ์ฒ๋ฆฌ
temp[L] = arr[i];
DFS(L+1);
visited[i] = 0 // ๋ฐฉ๋ฌธ ํ ๋ค์ ์ฌ๋ผ๊ฐ ๋ ์์๋ณต๊ตฌ
}
}
}
}
DFS(0)
return answer;
}