DFS 와 순열

문제

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

예시

numbers : [3,6,9]
M : 2
result :
3 6
3 9
6 3
6 9
9 3
9 6

풀이

• 이전에 풀었던 중복순열 의 응용 문제이다.
  
• 위 그림이 이 문제에서 도출해야 할 결과인데, 숫자 옆의[n] 은 해당 숫자가 numbers에서 몇 번째 인덱스에 있는지 나타낸다.
  
• 나는 순열 하나가 만들어질 때마다 temp 배열에 넣어 최종 answer에 전달하기로 했다.
  
• 최종 answer 에 가장 먼저 추가되어야 할 [3, 6] 부터 살펴보면, temp=[3,6] 을 실행하고 싶다고 했을 때 temp 의 0번째, 1번째, ... M 번째 인덱스 까지의 값을 채워야 M 개를 선택했다고 할 수 있다. (이 풀이에서는 M === 2 로 가정)
• 깊이 L 이 0일 때 for문을 돌면서 temp에 numbers의 i 값을 넣고 DFS(L+1) 을 실행하면, temp[0] === [3, 3] 이 되고 만다. 이 문제는 중복순열 문제가 아니므로 중복된 값이 temp에 들어가서는 안된다.
  
• 그래서 DFS로 노드를 파고 들어가면서 이미 방문했던 노드에는 방문하지 않도록 하는 ch 배열을 만들었다.
  
• 이제 temp[L] = numbers[i](1) 와 DFS(L+1)(2) 를 무작정 실행하는게 아니라, ch 배열의i번째 인덱스가 0 일 때 (방문한 적 없을 때)만 (1) 과 (2)를 실행하도록 했다.
• 이를 통해 temp[3, ?) 에서 ? 에 값을 채울 때, 3은 이미 이전 깊이에서 방문했다고 체크해뒀으므로, ? 의 후보군에서 3은 빠질 수 있는 것이다.

회고

• 메인 로직과 별개로 따로 체크 배열을 두고 메인 로직에 참여시킨다는 개념이 아직은 생소하지만 그래도 뭔가 신기한 것 같다.
• DFS 내에서 for문 을 사용할 때의 코드 흐름을 완벽히 따라가려면 아직은 멀은 것 같다.

코드

const solution = (numbers, M) => {
	const answer = [];
	const temp = [];
	const ch = Array.from({ length: numbers.length }, () => 0);

	const DFS = L => {
		if (L === M) {
			answer.push([...temp]);
		} else {
			for (let i = 0; i < numbers.length; i++) {
				if (ch[i] === 0) {
					ch[i] = 1;
					temp[L] = numbers[i];
					DFS(L + 1);
					ch[i] = 0;
				}
			}
		}
	};

	DFS(0);
	return answer;
};