[완전탐색][트리] - 순열 구하기(DFS)

문제

1부터 n까지의 m개의 순열을 구하라

문제 풀이

def DFS(L):
    global cnt
    if L == m:
        for i in range(m):
            print(res[i],end =" ")
        print()
        cnt += 1
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                res[L] = i
                DFS(L+1)
                ch[i] = 0
        

if __name__ == "__main__":
    n, m = map(int,input().split())
    res = [0] * n
    ch = [0] * (n+1)
    cnt = 0
    DFS(0)
    print(cnt)

• 중복 수열과 다르게 이번엔 중복된 값 없이 진행해야 하기에 check를 위한 리스트를 만들어 해당 노드가 앞에 나온다면 다시 나오지 못하게 막아준 뒤 stack에 들어간 해당 함수가 끝나면 다시 다음 판단을 위해 check를 풀어주는 형식으로 풀이를 진행한다.