[김태원 알고리즘] 순열 구하기 (DFS)

사용 언어: Python3

문제

풀이

def DFS(L):
    global cnt
    if L == M:
        cnt += 1
        print(' '.join(map(str, res)))
    else:
        for i in range(1, N+1):
            if used[i] == 1: # 이미 사용한 원소는 사용하지 않기
                continue
            used[i] = 1 # ✅ i 원소를 사용했음을 체크
            res[L] = i
            DFS(L+1)
            used[i] = 0 # ✅ DFS 호출 이후 back 할 때 사용한 원소 체크 해제 (되돌리기)

N, M = map(int, input().split())

used = [0] * (N+1) # ✅ 중복을 허용하지 않기 위해 사용한 원소 체크
res = [0] * M
cnt = 0

DFS(0)
print(cnt)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기