15649: N과 M (1)

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

15649번: N과 M (1)

설명

자연수 N과 M이 주어졌을 때, 다음 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램 작성. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열이다. 

• 한 줄에 하나씩 문제의 조건을 만족하는 수열 출력
• 중복되는 수열을 여러 번 출력하면 안된다.
• 각 수열은 공백으로 구분해서 출력
• 수열은 사전 순으로 증가하는 순서로 출력.

핵심 아이디어

• 백트래킹은 DFS를 사용하여 풀 수 있는데, 일반적인 DFS와의 차이점은 가지치기를 한다는 점이다. 즉, 모든 경우의 수를 담색하는 대신 조건을 걸어서 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서(BACK) 다른 경우를 탐색하는 것이다. 따라서 DFS는 모든 경우를 탐색하는 반면 백트래킹은 조건에 부합하지 않으면이전 노드로 돌아가서 다른 경우를 탐색하는 것이다. 모든 경우를 탐색하지 않는다. 
• 예를들어, 123을 찾는 다고 가정했을 때 후보는 [132, 234, 123] 이 있다. 이 수 중에서 백/십의 자리 숫자가 다르면 굳이 일의 자리까지 탐색할 이유가 없다.

코드 구현

1. 길을 가다 조건에 부합하지 않으면 왔던 길로 되돌아가 다른 경로 탐색
2. 보통 재귀로 구현하며 조건에 맞이 않으면 종료한다.
3. DFS(깊이 우선 탐색)기반

import sys
input = sys.stdin.readline

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

arr = [] # 수열을 저장할 리스트

def dfs():
	if len(arr) == m:
		# 한 줄에 하나씩, 각 수열은 공백을 구분해서 출력
		# 사전 순으로 증가
		print(' '.join(map(str, arr)))
		return
	else:
		for i in range(1, n+1):
			if i not in arr:
				arr.append(i)
				dfs() # 재귀적으로 다음 숫자 탐색
				# dfs() 함수 호출이 끝나면
				# 다음 탐색을 위해 이전 노드로 돌아간다.
				arr.pop()
dfs()