N과 M (1)

백준 15649

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력

입력	출력
3 1	1 2 3
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

---

접근 방식

: 순서 중요. permutations 이용

알게된 점

재귀 및 백트래킹으로 풀 수 있다.

코드

백트래킹 이용

def dfs(depth):
    if depth == m:
        print(*arr)
        return
    
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = 1
        arr.append(nums[i])
        dfs(depth+1)
        visited[i] = 0
        arr.pop()

n, m = map(int, input().split())
nums = [i for i in range(1, n+1)]
visited = [0]*n
arr = []
dfs(0)

순서가 중요할 때에는 stack과 방문처리를 해줄 리스트를 사용하는 것 같다.
for문을 돌면서 방문하지 않았으면 방문 처리를 해주고 스택에 원소를 넣은 다음 깊이 탐색을 한다.
탐색이 끝나고 나면 다시 방문 처리를 안한것으로 바꿔주고 리스트에서 pop한다.