[Algorithm] 순열 구하기(DFS)

❐ 순열 구하기

▶︎ 문제

   10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 

   입력으로 M과 N개의 자연수가 오름차순으로 정렬된 배열이 주어집니다. 

 

▷ 입력 예제

2, [3, 6, 9]

 

▶︎ 출력 예제

3 6
3 9
6 3
6 9
9 3
9 6

 

▶︎ 문제 설명

순열은 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 나열하는 것을 말한다. 이전 포스팅에서 중복순열은 중복을 허용하기 때문에 3 3과 같은 경우의 수가 가능했던 반면, 순열에서는 이것이 허용되지 않는다. 

 

▷ 내 답안

function solution(m, arr) {
    let answer = [];
    let n = arr.length;
    let ch = Array.from({ length: n }, () => 0);
    let tmp = Array.from({ length: m }, () => 0);
    
    function DFS(L) {
        if (L === m) {
            answer.push(tmp.slice());
        } else {
            for (let i = 0; i < n; i++) {
                if (ch[i] === 0) {
                    ch[i] = 1;
                    tmp[L] = arr[i];
                    DFS(L + 1);
                    ch[i] = 0;
                }
            }
        }
    }
    DFS(0);
    return answer;
}

let arr = [3, 5, 6, 9];
console.log(solution(2, arr));

 

let ch = Array.from({ length: n }, () => 0);
let tmp = Array.from({ length: m }, () => 0);

코드에서 사용된 배열 ch와 tmp 배열의 쓰임을 이해하는 것이 중요하다. ch는 'checked' 라는 의미로 배열에서 해당 인덱스의 숫자가 이미 사용되었는지 아닌지를 기록하는 역할을 한다. 중복순열을 구현할 때와 다르게 이 장치가 필요한 이유는 한 번 고른 숫자는 하나의 경우의 수 안에서 다시 고를 수 없기 때문이다. 

 

ch[i] = 1;

특정 인덱스의 숫자가 사용되었다면 그 값을 1로 변경하여 사용된 숫자임을 마킹한다. 

DFS(N+1)호출은 해당 인덱스의 숫자가 이미 선택된 적이 있는지를 if문으로 검사한 후 진행된다.

// 인덱스 값이 0인 경우에만 코드 실행
if (ch[i] === 0) {
	...
}

1로 마킹하는 것에서 끝나는 것이 아니라 해당 DFS(L)이 다 돌았다면 자녀 노드에서 부모 노드로 회귀할 때 다시 0으로 값을 초기화 해주어야 다음 연산에서 활용할 수 있다. (할 게 많다....)

ch[i] = 0;

 

 

tmp는 'temporary'로, 선택된 숫자들을 기록한다. 이 문제에서는 2개를 뽑아 나열하므로 배열의 크기 역시 m, 즉 2가 된다. 

DFS(N)에서 N이 일정한 크기에 다다르면 tmp에 저장된 값을 얕은 복사를 통해 answer에 저장한다. 

if (L === m) {
    answer.push(tmp.slice());
}

 

이 과정을 그림으로 도식화한다면 다음과 같다.