[리트코드] Permutations(python)

리트코드, Permutations_순열

TL;DR

• DFS(깊이 우선 탐색)

문제 분석

1. 주어진 숫자 배열에 대해 만들 수 있는 모든 순열을 반환하라.
2. 반환된 배열은 어떤 순서로 되어 있어도 상관 없다.

 

- 주어진 숫자들로 만들 수 있는 순열을 반환하면 된다.

입출력 형태

입출력 예시

풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        
        def dfs(v: int, permutation: List[int] = []):
            permutation.append(v)
            
            if len(permutation) == len(nums):
                answer.append(permutation)
                return
            
            for num in nums:
                if num not in permutation:
                    dfs(num, permutation[:]) # value !
                    
            
        for num in nums:
            dfs(num, [])

        return answer

 

재귀적인 방법의 DFS를 사용한 풀이 방법이다. 방문한 정점을 기준으로 순열을 만든다.

이 코드에서 중요한 부분은 재귀적인 호출이 일어나는 부분에서`permutation[:]`의 형태로 인자를 넘겨주는 것이다. 파이썬은 기본적으로 객체로 구성되어 있어 변수에 값을 할당하게 되면 주소를 참조하는 형태로 값이 할당되게 된다. 주소를 참조하는 형태로 값을 넘기게 되면 각 순열을 생성할 때마다 값이 permutation 배열에 계속 반영되게 되어 문제가 발생한다. 이를 단순 값을 넘겨주어야 재귀적인 호출이 일어날 때 수행하는 각 연산이 모든 경우에 대해 적용되는 것이 아닌 개별의 경우에 대해서 적용되게 된다.

배열을 인자로 주어질 때 [:]를 붙여서 보내게 되면 해당 배열의 주소가 아닌 값 자체를 인자로 넘기게 되어 이것이 가능하게 되는 것이다.

 

코드의 동작을 살펴보면 아래와 같다.

- dfs를 최초 호출하는 부분에서는 주어진 각 숫자들을 처음 방문한 노드로 두고 시작한다.

- dfs가 수행되게 되면 순열을 저장할 배열에 방문 노드를 넣고, 순열 배열의 길이가 주어진 숫자의 길이과 같은지를 확인하고, 같다면 정답 배열에 넣고 종료한다.

- 그렇지 않다면 입력으로 주어진 숫자들에서 방문한 노드를 제외한 숫자들에 대해 dfs를 재귀적으로 수행한다. 이 때, 방문한 노드의 정보가 담긴 permutation의 값을 같이 전달해준다.

- 각 dfs가 종료되게 되면 순열이 정답 배열에 들어가게 되어 답을 얻을 수 있다.

 

이 문제는 스택을 활용한 구현으로는 풀지 못하였다. 추후에 스택으로 구현하게 된다면 추가할 예정이다.