백준 15649번 - N과 M(1)

완전 탐색중의 한 방법인 백트래킹 알고리즘에 대한 문제이다. 백트래킹의 특징은 탐색과정 중에 정답이 될 수 없는 조건에 해당되면 가지치기(Pruning)하여 효율을 높일 수 있다는 점이다. DFS와 유사하지만 DFS는 불필요한 경로를 사전에 차단할 수 없기 때문에 경우의 수를 줄이지 못한다. 

백트래킹 문제는 트리를 그리면서 풀면 이해가 더 잘 된다. 예제 입력 2의 경우에, 각 숫자(부모 노드)에는 자식노드 1,2,3,4가 있는데, 정답이 아닌 조건(자기 자신 ex) 1 1 , 2 2,..)이면 다시 되돌아가서 진행(가지치기)해준다.

1부터 N까지 돌면서 M만큼 출력을 해줘야 한다. 그러므로 M 만큼의 배열을 선언해서 하나씩 넣어준 뒤 출력하고 다시 빼주는 식으로 코드를 짜면 되겠다. 

s는 탐색하면서 append됐다가 pop되기 위한 배열인데, 이미 s 안에 i 즉, 자기 자신이 있으면 넘어가주면서 진행한다.

배열의 크기가 M일 때 출력을 해주면 되겠다.

##함수 선언 부분
def NPM(s):
    if len(s) == M:
        print(' '.join(map(str,s)))

    for i in range(1, N + 1): #1부터 N까지
        if i in s: #이미 i가 있으면  #가지치기
            continue #넘어간다
        s.append(i)
        NPM(s) #탐색
        s.pop() #탈출

##변수 선언 부분
data = []

##메인 함수 부분
if __name__ == "__main__":
    N, M = map(int,input().split())
    NPM(data)

재귀함수를 이용해서 구현하는 것이 낯설어서 시간이 좀 걸렸던 문제다. 백트래킹을 살짝 맛본 정도