[백트래킹] BOJ 15649번 - N과 M(1)

문제

https://www.acmicpc.net/problem/15649

풀이

각 자리 별로 올 수 있는 숫자를 파악한다.
만약 N = 5, M = 4라고 한다면 다음과 같이 생각한다.

각 자리 별로 가져올 숫자를 구하는 과정에서 재귀 함수를 사용한다.

코드

방법 1) 백트래킹으로 풀이

# N : 1부터 N까지의 숫자를
# M : 조합해서 길이가 M인 숫자를 만들어라

N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M:
        # 숫자 배열 print
        print(" ".join(map(str, ans)))
        return      # ans 값을 출력하면 return (다시 새로운 배열 생성)
    
    for i in range(1, N+1):
        if i not in ans:
            ans.append(i)
            back()      # 재귀 (계속 뒤에 새 숫자 가져옴)
            ans.pop()       # 가장 마지막에 들어온 숫자를 뺌 (전 단계로 돌아감)

back()

방법 2) itertools 라이브러리를 활용 (permutations)

from itertools import permutations

N, M = map(int, input().split())
ans = permutations(range(1, N+1), M)

for i in ans:
    print(" ".join(map(str, i)))

📚 참고 : https://veggie-garden.tistory.com/24

• 알고리즘 구현 방식 생각
• 백트래킹과 DFS의 차이