DFS로 순열 구현하기 - 2021/05/03

예를 들어, arr=[1,2,1,3]일 때, 4개를 뽑는 순열을 구현하려면 DFS를 이용하여 만들 수 있다.

 

arr=[1,2,1,3]
a=''
result=[]
visited=[0]*len(arr)

def dfs(idx):
    global a
    if idx==len(arr):
        result.append(a)
        return
    for i in range(len(arr)):
        if visited[i]==0:
            visited[i]=1
            a+=str(arr[i])
            dfs(idx+1)
            visited[i]=0
            a=a[:-1]
            
dfs(0)

편의를 위해 문자열로 저장했다.

 

우선 dfs를 이용하는데 기본적으로 dfs는 탈출조건문과 계산식 두가지를 써야한다. (탈출조건식을 flag로하게되면 한개를 더 써야한다.)

자리 체크를 해줄 visited배열을 만들고 방문처리 후 그 값을 추가한다 그리고 dfs에 index를 1추가하여 넣고 방문처리를 해제하고 값에서도 추가한 값을 빼준다.