[리트코드 46] DFS를 활용한 순열 문제풀이

잠시 고등학교 수학시간에 배운 내용을 되새겨보면..

순열(permutation)이란? 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것.

순열의 수 수식은 nPr = n!/(n-r)! 으로 여기서 팩토리얼(!)이란 서로 다른 n개를 나열하는 경의 수를 의미한다. 기호로는 n! 으로 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수의 곱이다. (n! = n(n-1)(n-2)(n-3)...1)

 

46. 순열(Permutation)

Example

주어진 서로 다른 정수의 배열로 가능한 모든 수열을 출력하라. (순서는 상관 없음)

Constraints

- 1 < nums.length <= 6

- -10 <= nums[i] <= 10

- 배열(nums)의 정수는 모두 고유하다.

Solution

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

 

위 예제를 순열 수식에 대입해보면 3!/(3-3)! = 3! = 3*2*1 이므로 쉽게 6개의 경우의 수를 구할 수 있다. 하지만 요구하는 답은 경우의 수가 아니므로 모든 가능한 경우를 그래프 형태로 나열하면 다음과 같다.

순열 경우의 수 그래프

 

위 그래프에서 리프 노드(leaf node) 즉, 마지막 노드의 값이 순열의 최종 결과이다. 이때 자식 노드의 개수를 살펴보면 root 노드는 3개 그 다음은 2개, 1개 순으로 작아지는 걸 볼 수 있다. 이는 위에서 풀이한 순열이 수식(3! = 3*2*1)과 동일하다. 예를 들어 입력값이 4개라면 root 부터 자식 노드의 개수는 4*3*2*1 로 순열의 경우의 수는 24개가 될 것이다.

이제 위 그래프를 DFS 탐색 알고리즘으로 풀이해보면 for문을 돌며 이전 값을 하나씩 덧붙여 계속 재귀 호출을 진행하다 리프 노드에 도달한 경우 즉, elements 의 개수가 0이 된 지점에 결과에 추가한다.

 

prev_elements 배열 상태 변경

 

아래 코드 샘플에서 prev_elements 배열의 변화를 도식화해보면 위와 같이 깊이 우선 탐색(DFS) 방식으로 리프 노드까지 탐색이 끝나면 결과(answer)에 담고 pop() 하여 다음 노드를 탐색한다.

코드 샘플

# python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        prev_elements = []
        
        def dfs(elements):
            # 리프 노드일 때 이전 값을 정답에 추가한다.
            if len(elements) == 0:
                answer.append(prev_elements[:])
            
            # 순열 생성
            for e in elements:
                # 이전 값을 하나씩 덧붙인다.
                prev_elements.append(e)
                
                # 자기 자신은 제외한 새 배열 리턴
                dfs([n for n in elements if n != e])
                
                # 이미 탐색이 끝난 노드는 제거한다.
                prev_elements.pop()
            
        dfs(nums)
        return answer

 

여기서 중요한 부분은 Python 에서 list 자료형은 mutable(가변) 이기 때문에 정답에 추가할때 그냥 answr.append(prev_elements) 로 처리하게되면 래퍼런스가 추가되어 참조된 값이 변경될 경우 같이 변경되게 된다. 그럼으로 참조 관계를 갖지 않도록 copy(), deepcopy() 등을 사용하여 객체를 복사해서 추가해야한다.  *dictionary도 가변형이다.

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview