15650 N과 M(2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.입력
• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 출력
• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

백트래킹에 오름차순조건을 추가한 문제였다.

 

기존 백트래킹은 일단 dfs를 활용하고,  visited를 bool변수로 이용해서 이미 선택된 번호를 거르게 해주는 가지치기가 필요하다. 

오름차순이 되기 위해서는 result의 마지막 수보다 항상 커야한다는 조건을 걸었다.

 

이때 result에 원소가 하나도 없는 경우를 고려해서 조건을 추가했다.

 

풀이

 

 

N,M=map(int,input().split())
result=[]#정답 출력용
visited=[False]*(N+1)#가지치기용. 갈필요없는 길을 막아준다.

def dfs(N,M,depth): #depth= M개까지 출력했는지 확인하려고.
    if depth==M+1:
        for i in result:
            print(i,end=" ")
        print()
        return

    for i in range(1,N+1):
        if not visited[i] :
            if len(result)!=0 and result[-1]>i:
                continue

            visited[i] =True
            result.append(i)
            dfs(N,M,depth+1)
            visited[i]=False
            result.pop()

dfs(N,M,1)