JS 알고리즘 - DFS로 부분집합 구하기

 

DFS 이해하기

 

오늘의 자바스크립트 알고리즘을 풀던 중 잘 이해가 안가는 DFS를 결국 이해해서 블로그에 올려본다.

 

 

아직 보기만해도 무서운 DFS 구조

 

 

 

문제는 자연수 N이 주어지면 해당 자연수의 부분집합을 DFS로 구현하는 것이었고, 해답은 아래와 같다.

 

DFS 해답

   function solution(n) {
            let answer = [];
            let ch = Array.from({ length: n + 1 }, () => 0);
            console.log(ch)
            function DFS(L) {
                console.log(`n: ${n}, L: ${L}`)
                if (L === n + 1) {
                    console.log(`if ${L} === ${n + 1}`)
                    let tmp = "";
                    for (let i = 1; i <= n; i++) {
                        if (ch[i] === 1) tmp += (i + " ");
                        console.log(`ch: ${ch}, ch[i]: ${ch[i]}`)
                        console.log(`tmp: ${tmp}, i: ${i}`)
                    }
                    if (tmp.length > 0) answer.push(tmp.trim());
                }
                else {
                    console.log(`!if ${L} === ${n + 1}`)
                    ch[L] = 1;
                    DFS(L + 1);

                    ch[L] = 0;
                    DFS(L + 1);

                }
            }
            DFS(1);
            return answer;
        }

        console.log(solution(3));

 

이해가 안갔던 개념들

 

나는 위 해설에서 몇 가지 부분이 이해가 되지 않았다.

아래서 하나씩 기술하겠다.

 

 

Q. 왜 ch배열이 n+1인가?

A. 그냥 배열의 인덱스 숫자와 일치시켜서 보기 좋게 하려고

 

 

예를 들어, n=3일 때, 숫자들은 1, 2, 3이다. 이 숫자들을 ch 배열의 인덱스와 일치시키려면, ch[1]이 숫자 1에 대한 정보를, ch[2]가 숫자 2에 대한 정보를, 그리고 ch[3]이 숫자 3에 대한 정보를 가지게 된다. 이렇게 하면 프로그램을 작성하고 이해하는 데 훨씬 더 직관적이고 편리하다고.

 

위 예시를 표로 구현하면 아래와 같다. 인덱스 0은 사용되지 않고, 인덱스 1,2,3은 각각 숫자 1,2,3의 부분집합 포함 여부를 나타낸다. 값 행에서 1은 포함, 0은 비포함, - 은 아직 결정되지 않았다는 뜻이다.

인덱스	0	1	2	3
값	-	1	0	1

 

 

 

 

 

Q.  "if (L === n + 1) { //생략 }" 왜 이 부분이 재귀의 종료조건인가?

A. 이 재귀 알고리즘은 숫자 1부터 n까지 각 숫자를 부분집합에 포함시킬지 말지를 결정한다.

 

여기서 L은 현재 처리하고 있는 숫자의 단계를 나타낸다.

예를 들어, n=3이라면, 숫자 1, 2, 3 각각에 대해 이 결정을 해야 한다.

 

• 처리 과정: L = 1에서 시작하여, 숫자 1을 부분집합에 포함시킬지 말지 결정하고, 그 다음 L = 2로 넘어가 숫자 2에 대해 같은 결정을 한다. 이어서 L = 3에서 숫자 3에 대해 결정한다.
• 종료 조건: L이 n+1이 되면, 이는 모든 숫자에 대한 결정(포함시킬지 말지)이 끝났음을 의미한다. 예를 들어, n=3일 때, L = 4가 되는 순간 모든 숫자(1, 2, 3)에 대한 결정이 끝났다는 뜻이다.

 

 

 

 

Q. 재귀가 종료된 후 아래 코드를 처리하는 이유

 for (let i = 1; i <= n; i++) {
                        if (ch[i] === 1) tmp += (i + " ");
}

 

A. 1번에서 언급한 표를 좀 더 구체화하여 설명 가능하다.

인덱스	0	1	2	3
값	-	1	0	1
부분 집합 포함 여부	-	예	아니오	예
tmp에 추가되는 값	-	"1"	(추가 안됨)	"1 3"

 

결과적으로, 이 코드는 ch 배열을 사용하여 해당 순간의 부분집합을 문자열 형태로 구성하고, 이를 최종 결과 리스트에 추가하는 역할을 한다.