[백준] 15649. N과M (1)

백트래킹의 기본원리를 알 수 있다.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

1. visited 리스트 만들기 (중복방지)
2. depth, n, m을 입력받는데 이때, depth는 answer의 길이.
3. depth가 m과 같아진다면 함수가 종료된다.
4. depth와 m이 같지 않다면 아직 탐색해야 할 숫자가 남았다는 의미이므로 visited에 False값이 저장되어 아직 방문하지 않은 숫자를 방문한다.
4-1. 방문한 숫자는 방문했다는 의미로 visited에 True를 저장해주고 depth를 1증가시킨 상태에서 재귀함수를 실행한다.
5. 함수를 다시 실행하면 금방 방문한 숫자를 answer배열에 저장하고 해당 함수에서 나오게 되면 방문했다는 표시를 다시 False로 바꿔주고 해당 숫자를 pop해주어야 원래 자리로 돌아가서 다음 탐색을 할 수 있게 된다.

n,m=map(int,input().split())
answer=[]
def dfs(depth,n,m):
    if depth==m:
        print(*answer)
        return
    for i in range(1,n+1):
        if not visited[i]:
            visited[i]=True
            answer.append(i)
            dfs(depth+1,n,m)
            visited[i]=False
            answer.pop()
visited=[False]*(n+1)
dfs(0,n,m)