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;
};
Author And Source
이 문제에 관하여(DFS 와 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/DFS-와-순열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)