[백준/Python] - 15649번 N과 M(1)

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

 

 

제출코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ans = []

def backtracking():
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return
    # 1 2 3 4
    for i in range(1, N+1):
        # 1일때
        # ans는 빈배열이니 ans에 1 append
        if i not in ans: #중복확인
            ans.append(i)
            backtracking()
            ans.pop()
backtracking()

 

백트래킹 알고리즘을 공부하면서 풀어보니까 이해가 쭉쭉된다.

백트래킹이란?

우선 백트래킹은 탐색 알고리즘으로 가능한 모든 경로를 따라 들어가 탐색한다. 원하는 값이 나오지 않으면 더이상 탐색하지 않고 뒤로 돌아가는 알고리즘으로 왔던 길을 다시 되돌아가는 알고리즘이라고 생각하면된다.

 

처음 예제 말고 두번째 예제로 풀어보면 이해가 잘 된다.

위 사진과 같은 방법으로 

1. 반복문에서 1을 뽑는다. 중복검사를 하여 1이없으면 ans에 append하고, 재귀호출을 한다.
2. 재귀호출한 함수에서 1부터 N까지 또 반복한다. 1은 있고 2는 없으므로 2를 ans배열에 append한다.
3. 다음 재귀호출에서 backtracking함수는 기저조건을 만족하므로 ans배열 출력 후 함수 탈출한다.
4. 그다음 ans배열에서 2는 pop된다.

M의 길이가 2일때는 

• 첫번째 depth 
• 두번째 depth
• 세번째 depth

한번 찾을 때 세번의 함수가 호출된다. 

 

---

한줄평

재귀함수보다는 백트래킹이 더 이해하기 쉬웠다.

아직 백트래킹 초반부라서 그런가..?