[DFS] 순열(permutation)

1.  문제

■ DFS를 이용하여 리스트의 순열을 구현한다.

 

2. 핵심요약

■ DFS 알고리즘 활용법을 알아보자.

 

3. JavaScript 코딩

// 주어진 배열 arr과 방문 여부를 추적할 visited 배열을 초기화
let arr = [1, 2, 3, 4, 5];
let visited = new Array(arr.length).fill(false); // arr 길이만큼 false로 채운 배열 생성
 
let result = []; // 결과를 저장할 배열
 
// 깊이 우선 탐색(DFS)을 수행하는 함수
const dfs = (depth) => {
    // 종료 조건: 모든 원소를 선택했을 때
    if (depth === arr.length) {
        console.log(result); // 결과 배열을 출력
        return result; // 결과 반환
    }
 
    // 배열의 각 원소를 순차적으로 처리
    for (let i = 0; i < arr.length; i++) {
        // 이미 방문한 원소는 건너뜀
        if (visited[i]) continue;
 
        visited[i] = true; // 현재 원소를 방문 처리
        result.push(arr[i]); // 결과 배열에 현재 원소 추가
 
        // 재귀적으로 DFS 호출 (다음 깊이로 이동)
        dfs(depth + 1);
 
        // 재귀 호출 후, 백트래킹: 방문을 해제하고, 결과에서 현재 원소를 제거
        visited[i] = false;
        result.pop();
    }
}
 
// DFS 탐색 시작
dfs(0);
 

 

4. 참고

https://languagestory.tistory.com/380

[DFS] 개념(Depth First Search; 깊이 우선 탐색) - 자바스크립트