[백준] 15649번 N과 M(1) (python)

1. 문제

https://www.acmicpc.net/problem/15649

2. 풀이

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 복잡한 고려 없이 쉽게 짤 수 있다는 것이 장점이다.

3. 코드

import sys

def backtracking():
      if len(arr) == m:
            print(' '.join(map(str, arr)))
            return

      for i in range(1, n + 1):
            if i in arr:
                  continue
            arr.append(i)
            backtracking()
            arr.pop()

n,m = map(int,sys.stdin.readline().split())
arr = []
backtracking()

백트래킹 문제는 처음이라 다른 분들의 풀이를 참고하며 이해하는 식으로 진행했다.
참고한 블로그 1
참고한 블로그 2
참고한 블로그 3