[알고리즘] 백트래킹(bk_15649)

백트래킹이란?

• 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정을 말한다.
• 해당 기준에서 모든 가능한 상태를 확인 했으면, 이전 단계로 회귀해서 다시 반복

예제 문제(백준 15649번 N과 M(1) )

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

예제 입력

# input -1 
3 1
# output -1
1
2
3

# input -2 
4 2
# output -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

# input -3
4 4
# output -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

생각한 알고리즘

• 현재 수열리스트의 index번째 위치에 현재 수열리스트 내에 존재하지 않는 숫자(1~N)를 채워 넣은 이후 index+1 번째에도 다음을 반복한다.
• 만약 수열리스트 개수가 M개라면, 출력한다.

## 백트래킹
# 입력
N, M = map(int, input().split())

# 배열 초기화
orders = []
for i in range(M):
    orders.append(0)
# 백트랙킹 함수
def back (idx,order_list) :
    ord_list = order_list[:]
    if(idx >= M) :
        # 완성된 수열 출력
        for i in range(M-1):
            print(ord_list[i],end = " ")
        print(ord_list[M-1])
    else :
        for i in range(1,N+1):
            # 중복이 아닌 수에 대해서만 수열 생성
            if(not i in order_list):
                ord_list[idx] = i
                back(idx+1,ord_list)

back(0,orders)