LeetCode #46. Permutations(순열) DFS(백트래킹, 재귀)로 풀어보자!

문제 설명

정수 배열 nums가 주어졌을 때, 가능한 모든 순열(permutation)을 반환하라. 순열은 원소들의 모든 가능한 순서를 의미한다.

입력 및 출력 예시

Example 1:

• Input: nums = [1, 2, 3]
• Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Example 2:

• Input: nums = [0, 1]
• Output: [[0, 1], [1, 0]]

Example 3:

• Input: nums = [1]
• Output: [[1]]

제약사항

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums의 모든 원소는 고유하다.

---

풀이 1: 백트래킹 (Backtracking) 사용

시간 복잡도

• 시간복잡도: O(n * n!) (n은 배열의 길이)
• T(n)=n!×(c1​×n + c2 ​+ c3​×n)
  • n!: 가능한 모든 순열의 수
  • c1​: 요소 선택 및 추가 연산의 상수 시간
  • c2​: 경로 완성 확인 및 결과 추가 연산의 상수 시간
  • c3​: 요소 제거 및 사용 여부 업데이트 연산의 상수 시간

핵심 아이디어

• 백트래킹을 통해 가능한 모든 경로를 탐색하고, 모든 경로가 완성되면 결과에 추가하는 방식으로 구현한다.

코드 구현

public class L_46_순열 {
    public static void main(String[] args) {
        L_46_순열 l46 = new L_46_순열();
        int[] nums = {1, 2, 3};
        System.out.println(l46.permute(nums));
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 백트래킹을 통해 모든 순열을 탐색
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    // 백트래킹을 통해 가능한 모든 경로 탐색
    private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {    // 1ms
        // 경로의 길이가 nums의 길이와 같아지면 결과에 추가
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // 현재 경로를 결과에 추가
            return;
        }

        // 모든 숫자에 대해 사용되지 않은 숫자를 경로에 추가
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 백트래킹: 이미 사용된 숫자는 스킵
                continue;
            }

            // 숫자를 경로에 추가하고 사용 상태 업데이트
            path.add(nums[i]);
            used[i] = true;

            // 재귀 호출을 통해 다음 단계 탐색
            backtrack(result, path, nums, used);

            // 이전 상태로 되돌리기
            path.remove(Integer.valueOf(nums[i]));      // 경로에서 현재 숫자 제거
            used[i] = false;                            // 숫자를 사용되지 않은 상태로 변경
        }
    }
}

설명

1. 초기화:
   • result 리스트는 모든 가능한 순열을 저장한다.
   • path 리스트는 현재까지 탐색한 경로를 저장한다.
   • used 배열은 각 숫자가 현재 경로에서 사용되었는지를 추적한다.
2. 백트래킹 과정:
   • 경로의 길이가 nums의 길이와 같아지면 현재 경로를 result에 추가한다.
   • for 루프를 통해 사용되지 않은 숫자를 경로에 추가하고, 재귀 호출을 통해 깊이 탐색을 진행한다.
   • 재귀 호출이 끝나면, 이전 상태로 돌아가며 숫자를 사용하지 않은 상태로 복원한다.
   • 각 단계에서 가능한 모든 요소를 고려하지만, 이미 사용된 요소는 스킵하여 불필요한 탐색을 줄인다.

---

풀이 2: 깊이 우선 탐색 (DFS) 사용

시간 복잡도

• 시간복잡도: O(n * n!) (n은 배열의 길이)
• T(n)= n! × (c1​×n + c2​×(n−1) + c3 ​+ c4​×n)
  • n!: 가능한 모든 순열의 수  
  • c1​: 맨 끝에 요소를 추가하는 평균적인 시간
  • c2​: 특정 위치에 요소를 추가하는 경우의 시간
  • c3​: 경로가 완성되어 결과 리스트에 추가하는 시간
  • c4​: 특정 위치에서 요소를 제거하는 경우의 시간

핵심 아이디어

• DFS를 통해 모든 경로를 탐색하며, 사용되지 않은 요소를 경로에 추가하는 방식으로 구현한다.

코드 구현

private void dfs(List<List<Integer>> results, List<Integer> path, List<Integer> elements) { // 2ms
    // 탐색해야할 elements가 비어있다면 재귀 종료 및 results에 path 저장
    if (elements.isEmpty()) {
        results.add(new ArrayList<>(path)); // 현재 경로를 결과에 추가, path 깊은복사
    }

    // 사용되지 않은 모든 요소에 대해 탐색
    for (Integer e : elements) {                                   
        List<Integer> nextElements = new ArrayList<>(elements); // 사용하지 않은 요소 복사(깊은 복사)
        nextElements.remove(e);                                 // 현재 요소를 제외하여 다음 탐색 준비
        path.add(e);                                            // 현재 경로에 요소 추가

        dfs(results, path, nextElements);                       // 다음 단계 탐색
        path.remove(e);                                         // 탐색 완료 후 현재 요소 제거
    }
}

설명

1. 초기화:
   • results 리스트는 모든 가능한 순열을 저장한다.
   • path 리스트는 현재까지 탐색한 경로를 저장한다.
   • elements 리스트는 현재 탐색에서 사용하지 않은 요소들을 저장한다.
2. DFS 과정:
   • elements가 비어 있으면 현재 경로를 results에 추가한다.
   • 각 요소를 경로에 추가하고, 해당 요소를 제외한 리스트로 재귀 호출을 통해 다음 단계 탐색을 진행한다.
   • 재귀 호출이 끝나면, 이전 상태로 돌아가며 경로에서 요소를 제거한다.
   • 가능한 요소 집합을 재귀적으로 줄여 나가면서 경로를 구성한다.

---

결론

• 학습 내용: 이번 문제를 통해 백트래킹과 DFS를 활용한 순열 생성 방법을 학습했다. 두 방법 모두 모든 가능한 경로를 탐색하며, 주어진 문제의 제약 조건을 만족한다.
• 향후 계획: DFS를 사용하는 문제를 더 풀면서 더 익숙해져야 할 것 같다. 아직 즉시 문제 해결법이 떠오르지는 않고, 재귀의 사용이 어렵게 느껴진다.

---

<현재 공부중인 알고리즘 도서>

자바 알고리즘 인터뷰 with 코틀린 (박상길 저)