34. Permutations

🎯 leetcode - 46. Permutations

---

🤯 DFS를 활용한 순열 만들기

📌 문제

- 파이썬 알고리즘 인터뷰 34번 문제
- 순열을 모두 구하여 출력하시오

📌 날짜

2020.02.04

📌 시도 횟수

failed

💡 Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        path = []

        def dfs(curr):
            # 리프 노드일때 결과 추가
            if len(curr) == 0:
                results.append(path[:])

            # 순열 생성 재귀 호출
            for e in curr:
                next = curr[:]
                next.remove(e)

                path.append(e)
                dfs(next)
                path.pop()

        dfs(nums)
        return results


s = Solution()
print(s.permute([1, 2, 3]))

💡 문제 해결 방법

• [1, 2, 3]에 대한 순열을 구하는 과정을 손으로 적어서 풀어보았다.
  
• 즉, 위 그림의 그래프를 DFS로 탐색한 순서가 곧 해당 문제에서 모든 순열을 찾는 과정과 같음을 알 수 있다.
  

✅ curr(e), next, path에 대한 설명
- curr(e) : 사용 가능한 숫자들(e는 사용 가능 숫자들 중 현재 추가하려는 숫자)
- next : 사용 가능한 숫자들에서 현재 추가하려는 숫자(e)를 뺀 나머지 숫자들. 
다음 재귀에서 새롭게 curr이 될 아이들이다.
- path : path는 각 재귀 호출마다 순열 조합이 저장되는 공간이다. 
만약 하나의 완전한 순열 조합을 만들었다면 results에 저장하고 path는 pop하여 
리프 노드에서 다시 상위 노드로 이동할 수 있게 된다.

✅ 재귀 tip 
- 재귀 호출을 하다가 리프 노드(더 이상 자식노드가 없음)를 만나게 되면 
리프노드의 결과를 results에 저장하고 리턴한다.
- 이때 저장할 때는 results.append(path[:])로 저장한다. (이유는 뒤에 나옴)

💡 새롭게 알게 된 점

✔ 왜 curr 대신 curr[:]을 사용했을까?
- 파이썬은 모든 객체를 참조하는 형태로 처리된다.
- 즉, curr을 전달하게 되면 참조된 값이 변경될 경우 같이 바뀌게 된다. 
- 따라서 순열 문제를 풀 때는 값만 복사되고 참조는 같은 형태로 전달되지 않도록 주의해야 된다.
- copy.copy(curr)라는 메소드를 사용할 수도 있지만 간단하게 curr[:]으로도 처리 가능하다.
>> next = copy.copy(curr)으로 사용해도 됨

❌ (한번에 맞추지 못한 경우) 오답의 원인

- DFS 이해하는데 오래 걸린다. 😥

---