백준 22.01.27. 15649번 - N과 M (1)

퇴각검색 - 위키백과, 우리 모두의 백과사전

---

arr = []


def dfs(n, m):
    if len(arr) == m:
        print(" ".join(map(str, arr)))
        return

    for i in range(1, n+1):
        if i not in arr:
            arr.append(i)
            dfs(n, m)
            arr.pop()


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

dfs(N, M)

• 백트래킹을 활용한 문제풀이입니다.
• 백트래킹은 브루트포스와 비슷하게 해를 얻을 때까지 모든 가능성을 시도합니다.
• 검색방법이 이진트리 검색방법과 상당히 유사합니다.

  

  퇴각검색 - 위키백과

• 깊이 우선 탐색(Depth First Search)를 사용합니다.
• 따라서 재귀함수로 구현되며 이는 dfs라는 이름의 함수로 선언했습니다.
  • arr은 모든 답을 담고있는 리스트가 아닌, 재귀를 통해 하나의 답을 담게되는 리스트라고 보면 편합니다. 
• dfs내의 반복문을 먼저 설명하자면
  
  1. 반복되지 않는 수가 검색됐을 때 준비된 arr리스트에 추가해줍니다.
  2. 재귀를 통해 반복되지 않는수를 다시 검색합니다.
  3. 재귀를 통해 진행하다보면 제일 처음으로 arr = [1, 2, 3, 4]가 될 것입니다.
  4. 이 때, dfs의 if문의 조건이 충족됩니다. 따라서 함수에 따라 출력되고 반환됩니다.
  5. 재귀가 풀린 arr[1, 2, 3, 4]는 pop() 메서드를 통해 arr[1, 2, 3]이 됩니다.
  6. arr[1, 2, 3]에서 3 = 세번째 재귀함수 반복문의 i값이므로 pop()된 후에 4번째 반복으로 넘어갑니다
  7. 따라서 arr[1, 2, 4]가 되며 다시 재귀를 통해 arr[1, 2, 4, 3]이 완성됩니다.
• 위 같은 과정을 통해 모든 답을 찾을 수 있습니다.

• 

• join메서드는 이터러블 객체의 요소들을 원하는 사잇값을 설정하여 이어주는 역할을 합니다.
  • ex) "*".join(["가나", "다라", "마바"]) = "가나*다라*마바"
  • 정답 코드에서는 int요소들을 str형식으로 바꾸기 위해서 map을 사용했습니다.