DFS로 순열 구하기

GGob2._.·2023년 6월 29일
0

algorithm

목록 보기
33/55

문제 설명

중복 순열이 아닌, 순열을 구해야 한다.

접근 방법

  • 특정 숫자를 사용했는지, 사용하지 않았는지 확인하는 배열을 활용하여 사용한 경우 넘기는 식으로 코드를 작성했다.
  • 이 역시 dfs 재귀가 끝난 뒤에는 다른 경우에서 활용할 수 있도록 사용안함 처리로 변경해야 한다.

작성한 코드

tmp = []

def DFS(L, n, m, ch):
    if L == m:
        for x in tmp:
            print(x, end =' ')
        print()
    else:
        for i in range(1, n+1):
            if ch[i] == 1:
                continue
            tmp.append(i)
            ch[i] = 1	# 숫자 사용 처리
            DFS(L+1, n, m, ch)
            tmp.pop()
            ch[i] = 0	# 숫자 비사용 처리
            

def solution(n, m):
    ch = [0] * (n+1)
    DFS(0, n, m, ch)
profile
소통을 잘하는 개발자가 되고 싶습니다.

0개의 댓글