백준 15649 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

이 문제를 풀기 전에 백트래킹에 대해서 먼저 알아보자.

 

백트래킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

 

필자가 문제를 풀어보며 느낀 건 백트래킹 문제는 dfs그래프를 사용하여 문제를 해결한다.

 

또한 재귀방식을 사용한다.

 

필자는 재귀함수에 약해 항상 가슴속 한 부분에서 외면해 왔는데, 이젠 진실을 마주할 때가 왔다.

 

또한 재귀 함수는 코딩할 때, 2가지부분으로 나뉘는 듯했다.

 

첫 번째, 탈출조건이다.

 

탈출조건을 사용함으로 원하는 목표치까지 도달했을 때 함수를 탈출함으로 재귀를 멈춘다.

 

두 번째, 논리절이다

 

재귀함수가 반복되며 수행될 기능이 작성된 부분이다.

 

코드

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

array = []

def dfs():

    if len(array) == m:

        print(' '.join(map(str, array)))

        return

   

    for i in range(1,n+1):

        if i in array:

            continue

        array.append(i)

        dfs()

        array.pop()

dfs()