18.DFS - 순열

https://leetcode.com/problems/permutations/

Permutations - LeetCode

 

이번 포스팅에서는 DFS를 이용한 순열에 대해서 정리해 보겠다

 

 순열은 다음 그래프처럼 DFS로 해결할 수 있다.

 

 풀이 방법에는 두가지 방법이 있다. 먼저 재귀구조로 문제를 풀어보겠다.

    def permute(nums):
        
        sol=[]

        def dfs(index,array):
            if len(array) == len(nums):
                sol.append(array)
                return

            for i in range(index,len(nums)):
                if nums[i] not in array:
                    dfs(index,array+[nums[i]])
                
        dfs(0,[])
        return sol

 설명하자면 array가 다 찰때까지 재귀적으로 빈 array 부터 파이썬의 list + list 연산을 이용해 재귀적으로 array를 한개씩 추가하는것이다. 순열이기 때문에 같은 원소들이 있어서 순서만 다르면 다른 원소로 취급하기 때문에 재귀적으로 호출되는 dfs 함수의 index 인자를 항상 0으로 시작하게 둔다. 여기서 추가중인 array에 중복되는 값이 있으면 그 구간을 pass 하게끔 처리를 해주었다.

 

 두번째 풀이는 파이썬의 itertools를 사용하는것이다.

    def permute(nums):
        return list(map(list,itertools.permutations(nums)))

 

 두번째 풀이가 더 쉽고 실행속도도 빠르다.