[Python] 백트래킹 / 백준 15649번

Backtracking(퇴각 검색)

- 해를 얻을 때까지 모든 가능성을 시도

- 깊이 우선 탐색 사용

- 재귀 함수로 구현

 

15649번 문제

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

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

• arr배열에 수열 저장
• isused배열을 이용하여 n까지의 각 수 이용 여부를 true/false로 저장 ([0]번은 사용 안함)
• func(x)는 arr[x]를 정하는 함수
• func()는 재귀함수

def func(x):
    if x==m:
        for i in arr:
            print(i, end=" ")
        print()
        return
    for i in range(1,n+1):
        if isused[i]==True:
            continue
        isused[i]=True
        arr[x]=i
        func(x+1)
        isused[i]=False

n,m=map(int, input().split())
isused=[0]*(n+1)
arr=[0]*m
func(0)

입력

4 3

결과

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

 

reference: 퇴각검색 위키백과

https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89