[알고리즘/백준] N과 M(1) 백트래킹 문제 풀이

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

15649번: N과 M (1)

 

문제 설명

• 1부터 N중 하나를 선택한 뒤
• 다음 1부터 N부터 선택할 때, 이미 선택한 값이 아닌 경우 선택
• M개를 선택 할 경우 프린트 

아이디어

• 백트래킹 재귀함수 안에서 for 문 돌면서 숫자 선택 ( 이 때 방문여부 확인)
• 재귀함수에서 M개를 선택할 경우 print

 

시간복잡도

• N!: 중복이 불가, N = 10까지 가능

자료구조

• 방문 여부 : bool[]
• 선택한 값 입력 배열: int[]

 

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

rs = []
chk = [False] * (n+1). #index와 숫자를 맞추기위해 +1

def recur(num):
	if num == m:
    	print(' '.join(map(str,rs)))
        return
    for i in range(1,n+1):
    	if chk[i] == False:
        	chk[i] = True
        	rs.append(i)
            recur(num+1)
            chk[i] = False
            rs.pop()
            
recur(0)

 

Tip

• 백트래킹 문제는 N이 작음 -> N을 확인하고 백트래킹을 사용할 지 말지 정할 수 있다.
• 재귀함수 사용할 때, 종료 시점 잊지말기!

 

 

 

 

 

참고- https://www.youtube.com/watch?v=atTzqxbt4DM