[백준 15649] N과 M(1) - Python (백트래킹, DFS, 순열)

 

15649번: N과 M (1)

 

 

<내 코드>

 

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색

            visited[i] = 0  # 탐사 완료 후 다시 초기화
            arr.pop()  # 탐사한 내용 제거


dfs(0)

 

DFS와 백트래킹을 이용해 푸는 문제다. 재귀가 사용되다 보니 이해를 하는데 꽤 힘들었다.. 

 

 

파이썬 itertools 모듈을 사용한 방법

 

from itertools import permutations

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

p = permutations(range(1, N+1), M)
for i in p:
    print(*i)