[Python] 백준 15649 N과 M (1) (Backtracking)

📌 문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

---

📌 풀이

💬 Code

import sys
input = sys.stdin.readline


def back_tracking(cnt):
    if cnt == m:
        for j in range(m):
            print(arr[j], end=' ')
        print()
        return

    for i in range(1, n + 1):
        if not isUsed[i]:
            arr[cnt] = i
            isUsed[i] = 1
            back_tracking(cnt + 1)
            isUsed[i] = 0


n, m = map(int, input().split())
arr = [0 for _ in range(10)]
isUsed = [0 for _ in range(10)]

back_tracking(0)

💡 Solution

백트래킹 문제 처음 풀어보는데 어렵다 ^_ㅠ..!

• arr: 숫자를 담을 리스트
• isUsed: 숫자 i를 썼는지 체크하는 boolean 리스트
• back_traking(cnt): 숫자를 cnt개 고른 상황에서 arr[cnt]를 정하는 함수

back_tracking(cnt)

재귀함수이므로 base condition을 설정해야 한다. cnt == m일 때, 즉 숫자를 m개 모두 골랐을 때 리스트의 원소를 출력하고 리턴한다.

그 외의 경우 1부터 시작해 n까지의 수 중 아직 사용하지 않은 수 i를 찾는다. 그리고 해당 수 i를 arr[cnt]의 값으로 지정한 후 i를 썼다는 의미에서 isUsed[i]를 1로 바꿔준다. arr[cnt]를 정했으므로 이제 arr[cnt+1]을 정하러 back_tracking(cnt+1)을 호출한다.

back_tracking(cnt+1)이 리턴되어 돌아오면 arr[cnt] 값이 i일 때의 모든 경우의 수를 탐색한 것이므로 i가 아닌 다른 값(예를 들어 h)일 때의 경우의 수 역시 탐색해주어야 하고, h로 시작해서 뒤의 원소에 i가 쓰일 수 있기 때문에 이를 위해 isUsed[i]를 0으로 비워준다.