순열
깊이 우선 탐색의 대표격인 순열 문제이다.
DFS 함수를 돌려 깊이가 순열의 크기에 도달할 때까지 다시 DFS를 반복적으로 시행하도록 처리해준다.
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(length: int, dfs_nums: List):
if length == len(nums):
res.append(dfs_nums)
return
else:
for val in list(x for x in nums if x not in dfs_nums):
print(f'dfs({length+1},{dfs_nums+[val]})')
dfs(length+1, dfs_nums+[val])
dfs(0, [])
return res
print(Solution.permute(Solution(),
[1, 2, 3]))dfs(1,[1])
dfs(2,[1, 2])
dfs(3,[1, 2, 3])
dfs(2,[1, 3])
dfs(3,[1, 3, 2])
dfs(1,[2])
dfs(2,[2, 1])
dfs(3,[2, 1, 3])
dfs(2,[2, 3])
dfs(3,[2, 3, 1])
dfs(1,[3])
dfs(2,[3, 1])
dfs(3,[3, 1, 2])
dfs(2,[3, 2])
dfs(3,[3, 2, 1])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
여기서 중요한 것은 dsf함수의 인자로 사용되는 dfs_nums를 직접적으로 바꾸면 안된다는 것이다.
예를 들어 초기답은 이랬는데,
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(length: int, dfs_nums: List):
if length == len(nums):
res.append(dfs_nums)
return
else:
for i in range(length, len(nums)):
dfs_nums.append(nums[i])
print(f'dfs({length+1},{dfs_nums})')
dfs(length+1, dfs_nums)
dfs(0, [])
return res
print(Solution.permute(Solution(),
[1, 2, 3]))dfs(1,[1])
dfs(2,[1, 2])
dfs(3,[1, 2, 3])
dfs(2,[1, 2, 3, 3])
dfs(3,[1, 2, 3, 3, 3])
dfs(1,[1, 2, 3, 3, 3, 2])
dfs(2,[1, 2, 3, 3, 3, 2, 2])
dfs(3,[1, 2, 3, 3, 3, 2, 2, 3])
dfs(2,[1, 2, 3, 3, 3, 2, 2, 3, 3])
dfs(3,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3])
dfs(1,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3])
dfs(2,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2])
dfs(3,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3])
dfs(2,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3])
dfs(3,[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3])
[[1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3], [1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3], [1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3], [1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3], [1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3], [1, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3]]
재귀적으로 dfs 함수가 돌때마다 dfs_nums 변수를 바꾸다보니 상황에 따라 초기화가 되지 않은 리스트로 커지게 되는 문제가 있었다. 따라서 재귀적으로 함수를 구성할 때는 변수 재할당을 매우 유의해야 한다.
조합
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
def dfs(length, dfs_nums):
if length == k:
res.append(dfs_nums)
return
else:
for val in list(x for x in range(dfs_nums[-1] if dfs_nums else 1, n+1) if x not in dfs_nums):
# print(f'dfs({length+1},{dfs_nums+[val]})')
dfs(length+1, dfs_nums+[val])
dfs(0, [])
return res
print(Solution.combine(Solution(), 5, 3))순열에서 이미 사용된 숫자는 같은 계층의 다음 탐색에서 버리기 위하여
for val in list(x for x in range(dfs_nums[-1] if dfs_nums else 1, n+1) if x not in dfs_nums):
와 같이 range를 dfs의 length가 바뀔 때마다 늘려주었다.
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
results = []
def dfs(elements, start: int, k: int):
if k == 0:
results.append(elements[:])
return
# 자신 이전의 모든 값을 고정하여 재귀 호출
for i in range(start, n + 1):
elements.append(i)
print(f'dfs({elements}, {i+1}, {k-1})')
dfs(elements, i + 1, k - 1)
elements.pop()
dfs([], 1, k)
return results
print(Solution.combine(Solution(), 5, 3))모범답안에 대한 이해는 추후 하는 걸로,,, 여기서는 start를 통하여 이미 쓰인 숫자를 제외한 숫자만을 재귀적으로 호출하느 ㄴ것으로 보인다.
