1. 문제

15649번

2. 풀이

• 이 문제는 백트래킹 알고리즘을 통해 풀어야 한다. 문제 풀이에 앞서 백트래킹 알고리즘에 대해 조사해 보았다. Chat GPT에 백트래킹 알고리즘에 대해 물어보면 다음과 같이 답변한다.

  백트래킹(Backtracking)은 모든 가능한 경우의 수를 탐색하여 해답을 찾는 알고리즘 중 하나입니다. 일반적으로 재귀적인 방법을 사용하여 구현됩니다.

  백트래킹은 주어진 문제의 조건을 만족시키는 가능성이 있는 모든 후보군을 탐색하고, 조건을 만족하지 않는 경우는 더 이상 진행하지 않고 이전 단계로 돌아가 다음 후보군을 탐색합니다. 이러한 과정에서 불필요한 탐색을 줄일 수 있어서 효율적인 탐색이 가능합니다.
  일반적으로 백트래킹 알고리즘은 다음과 같은 과정을 따릅니다.

  1. 상태 공간 트리(State Space Tree)를 생성합니다.
  2. 상태 공간 트리를 DFS(Depth-First Search) 방식으로 탐색합니다.
  3. 해를 찾거나 더 이상 탐색할 후보군이 없으면 이전 단계로 돌아가 다른 후보군을 탐색합니다.
  4. 모든 경우의 수를 탐색하면 알고리즘이 종료됩니다.

  상태 공간 트리는 주어진 문제에서 가능한 모든 상태를 나타내는 트리입니다. 각 노드는 특정 상태를 나타내며, 각 상태에서 가능한 후보군은 해당 노드의 자식 노드로 표현됩니다.

  백트래킹 알고리즘은 다양한 분야에서 사용됩니다. 예를 들어, 스도쿠, N-Queen, 지하수 탐사 등의 문제에서 백트래킹 알고리즘이 사용됩니다.

• 위 설명과 같이 코드를 짜 보았다.

N,M = list(map(int,input().split()))

def nm_backtrack(n, m):
    
    result = [] # 탐색한 경우의 수를 저장하는 상태공간 정의
    def backtrack(): # 상태공간을 DFS 방식으로 탐색
        if len(result) == m: # Depth가 tree 끝에 도달하면 값을 출력
            print(' '.join(map(str,result)))
            return # Depth가 tree 끝에 도달하면 재귀 종료

        for i in range(1,n+1): # 1부터 n까지 1씩 증가
            if i not in result: # i가 상태공간에 없을 때,
                result.append(i) # result에 추가한다.
                '''
                tree 가지를 재귀 형태로한번 더 뻗는다.
                위의 if문에 의해 Depth가 tree 끝에 왔다면
                출력하고 return 된다.
                '''
                backtrack()
                '''
                return되어 나온 tree의 가지 끝을 자른다.
                for 문에 의해 다음 i가 가지 끝에 나온다.
                '''
                result.pop()
                
    backtrack()

nm_backtrack(N, M)