DFS와 중복 순열

문제

지난 풀이 링크

예시

N	M	result
3	2	[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

풀이

• 중복 순열은 순열과 마찬가지로 n개 중에 r개를 순서에 상관 있게 뽑는데, 중복을 허락하여 뽑는 것을 말한다. (출처)
• DFS(L) 로 깊이(L)이 0부터 N 까지 깊어지는 함수를 만들면, L 은 만들어질 수열의 L번 인덱스가 될 수 있다.
• temp 라는 임시 빈 배열을 만들어 두고, temp 배열의 각 인덱스에 L 을 대입한다.
• 이를 통해 L 이 깊어질 때 마다 temp 배열의 각 인덱스를 가리키게 되는 것이다.
  
• 그렇다면 temp 배열의 각 값은 무엇으로 채워야 할까?
• DFS(L) 이 실행될 때 마다 1~N 까지 커지는 i 로 채워넣는다면, 아래와 같다.
  
• 눈여겨볼 점은, for문 안에서 i가 1씩 커질 때 마다 DFS(L+1) 을 실행해줘야 한다는 점이다. L의 깊이가 깊어져야 temp 배열의 다음 원소를 채울 수 있기 때문이다. (DFS 함수가 하나의 for문 인 느낌?)
• L의 값이 M과 같아진다면, temp 배열 내 M-1 개의 원소들에 값이 찼다는 의미이므로, 하나의 순열이 완성된 것이다.
  
• 여기까지 하면 DFS(M-1) 컨텍스트 에서 실행한 DFS(L+1) 의 함수 실행이 끝난 것이다.
• 애초에 DFS(L+1)을 for 문 안에 넣어서 실행했으므로, i 값이 1 늘어난 채 다시 DFS(L+1)이 실행된다.
  

회고

• DFS 함수는 계속 깊이가 더해지지만, 탈출 조건을 만나서 실행이 끝나면 원래 본인이 호출되었던 위치로 다시 돌아간다는 점이 가장 응용하기 어려운 점이었던 것 같다.
• 다음에는 콜스택을 직접 그려보면 좀 더 이해하기도, 설명하기도 쉬울 것 같다.

코드

const solution = (N, M) => {
	const temp = Array.from({ length: M }, () => 0);
	const answer = [];
	const DFS = L => {
		if (L === M) {
			answer.push([...temp]);
		} else {
			for (let i = 1; i <= N; i++) {
				temp[L] = i;
				DFS(L + 1);
			}
		}
	};

	DFS(0);
  	return answer;
};