백준 - 15649

문제 설명

자연수 N과 M이 주어졌을 때, 중복 없이 M개를 고른 수열을 모두 구하는 문제다.

접근 방식

• 처음 모든 수열을 고려하라는 조건을 보자마자 itertools의 permutations가 생각났고, 이를 이용해 간단하게 버전 1의 코드를 작성했다.
  -> permutations(범위, 수)를 이용한다.
  
  
• 문제가 백트래킹을 위한 문제이기 때문에, dfs와 유사한 방식으로 구현하고자 했다.
  
  
• 정답을 출력하기 위한 배열을 하나 선언하고, 1부터 n의 범위에서 배열에 값을 넣다 빼는 과정을 반복적으로 수행하며 배열의 길이가 m이 되었을 때 수열을 출력한다.
  
  
• for문을 이용해 수행되는 특성으로 문제의 조건인 사전 순서대로 출력은 신경쓰지 않아도 된다.

백트래킹 (Backtracking)

백트래킹은 DFS(Depth-Fist Search)의 방식을 기반으로하여, 불필요한 경우를 사전에 배제하며 원하는 답을 만날 때 까지 탐색을 수행하는 방식이다.

위 그림에서처럼, 수행하는데 모든 경우의 수를 탐색하는 브루트 포스와 비슷한것 같아 보이지만, 불필요한 경우는 애초에 탐색을 수행하지 않아 처리 속도에서 차이가 있다.

작성한 코드

• 버전 1. itertools의 permutatoins를 이용

import sys
from itertools import permutations          # 순열 생성

input = sys.stdin.readline

n, m = map(int, input().split())

result = permutations(range(1, n+1), m)     # 1 ~ n 까지의 범위에서 
                                            # m개의 가능한 모든 수열 추출
for i in result:
    print(" ".join(map(str, i)))            

• 버전 2. backtracking

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
result = []

def back(num):				# 백트래킹을 위한 재귀 함수
    if len(result) == m:	# 길이가 m이면 출력
        print(' '.join(map(str, result))) 
        return
    
    for i in range(1, num+1):	# 사용 가능한 자연수 범위 내에서
        if i in result:			# 배열에 문자가 있으면 넘어감
            continue
       
        result.append(i)		# 결과에 넣고 
        back()					# 재귀가 끝나면
        result.pop()			# 다시 빼줌

back(n)