[백준] 15650 N과 M(2) 파이썬 풀이 (백트래킹)

백준

 

문제

• 1~N까지 자연수 중에서 중복없이 M개를 고른 수열
• 고른 수열은 오름차순이어야한다.

 

 

문제 풀이

<백트래킹>

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.
• 어떤 노드의 유망성 점검 후 , 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색

1. 1부터 시작해서 그 숫자와 다음 숫자를 배열에 넣고 ,
2. 배열의 길이가 m이 되면 print하고 맨 뒤의 숫자를 pop한다.
3. 그 다음 숫자를 배열에 넣고 배열의 길이가 m이 되면 print하고 맨 뒤의 숫자를 pop한다
4. ...

 

 

 

코드

n,m = list(map(int,input().split())) #1234 2
s = []
def dfs(start): #start = 
    # print(f'dfs 호출시작, start = {start}')
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1): 
        if i not in s:
            s.append(i) 
            # print(f's.append = {s}')
            dfs(i+1)
            s.pop() 
            # print(f's.pop = {s}')
    # print(f'dfs호출 끝, start = {start}')
dfs(1)