문제링크 : https://www.acmicpc.net/problem/15650

N과 M(2)

풀이

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

# 루트 노드 : 1 ~ n-m+1
for i in range(1,n+1):
    dfs=[(i,1)]
    result=[]
    while dfs:
        # print("Dfs",dfs)
        # print("result",result)
        chk = dfs.pop()
        if result!=[] and chk[1]<=result[-1][1]:
            del result[chk[1]-1:]
            result.append(chk)
        else:
            result.append(chk)
        if chk[1]==m:
            for a in result:
                print(a[0],end=" ")
            print("")
        else:
            for i in range(n,chk[0],-1):
                dfs.append((i,chk[1]+1))

1부터 n까지의 자연수 중 m개의 중복 없는 조합을 찾으라는 문제였다. 기본적으로 DFS를 이용해 깊이가 m이 될때까지 탐색하며 m이되면 해당 값을 출력 후 다시 돌아오는 형식을 이용했다. DFS에 쓰이는 스택은 dfs라는 변수명을 사용하고 리스트로 대체했다. 해당 리스트에는 (값,깊이) 형식의 데이터를 넣었고 이 튜플값의 깊이가 m이 될때까지 탐색을 반복했다.