반응형
1. 문제
■ DFS를 이용하여 리스트의 조합(combination)을 구현한다.
2. 핵심요약
■ DFS 알고리즘 활용법을 알아보자.
3. JavaScript 코딩
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
let arr = [1, 2, 3, 4, 5]; // 주어진 배열
let result = []; // 결과를 저장할 배열
let combination = []; // 현재 조합을 저장할 배열
// 깊이 우선 탐색(DFS)을 수행하는 함수
const dfs = (startIndex) => {
// 종료 조건: 선택된 원소의 개수가 k개가 되면 조합을 결과에 추가
if (combination.length === 3) { // 예시로 3개 원소를 고르는 조합을 찾는 경우
result.push([...combination]); // 조합을 결과에 추가
return;
}
// startIndex부터 배열의 끝까지 순차적으로 탐색
for (let i = startIndex; i < arr.length; i++) {
combination.push(arr[i]); // 원소를 현재 조합에 추가
dfs(i + 1); // 다음 원소로 이동 (중복을 피하기 위해 i+1로 호출)
combination.pop(); // 백트래킹: 원소를 제거하고 다른 경우를 시도
}
}
// DFS 탐색 시작
dfs(0);
// 결과 출력
console.log(result);
|
cs |
4. 참고
https://languagestory.tistory.com/380
[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트
1. DFS(Depth First Search; 깊이 우선 탐색)의 개념■ 그래프에서 모든 노드를 한번씩 탐색하기 위한 방법■ 스택 또는 재귀함수를 이용하여 구현■ 루트 노드[또는 임의의 노드]에서 시작하여 형제(si
languagestory.tistory.com
반응형
'알고리즘(코딩테스트)' 카테고리의 다른 글
| [BFS] 개념(Breadth First Search; 너비 우선 탐색) - 자바스크립트 (0) | 2025.02.16 |
|---|---|
| 큐(Queue) 구현 및 테스트 (JavaScript, Python) (0) | 2025.02.16 |
| [DFS] 순열(permutation) (0) | 2025.02.16 |
| [백준][DFS][난이도:하] 단지번호 붙이기 (2667번) (0) | 2025.02.16 |
| [백준][DFS][난이도:하] 차이를 최대로 (10819번) (0) | 2025.02.16 |