백준 : 15649번 N과 M (1) [파이썬, 실버3, 백트래킹]

문제

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

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

 

입력

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

출력

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

예제

예제 입력 1

 3 1 # N, M > 1~3까지 자연수 중 중복 없이 1개를 고른 수열 모두

예제 출력 1

1
2
3

 

예제 입력 2

4 2 # 1~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

 

[문제 풀이]

* 백트래킹을 사용하여 풀이한다.

 

백트래킹이란?

: 백트래킹은 현재 상태에서 가능한 모든 경로를 탐색하다, 원하는 결과와 불일치하는 부분이 발생하면 탐색을 멈추고 전단계로 돌아가는, 즉 왔던 길 그대로를 다시 되짚어가는, backtrack하는 알고리즘이다.

 

백트래킹 vs DFS

둘 다 탐색을 하는 알고리즘이다.

 

백트래킹은 불필요한 탐색을 하지 않는다. 132, 234, 123, 총 3개의 요소를 가지고 있는데, 123이라는 값을 찾고 있다고 하자. 순서대로 132라는 값에 접근했을 때, 백의 자리 수가 동일하나, 십의 자리 수가 다르기 때문에 더 이상 탐색을 진행하지 않고 다음 수로 넘어간다.

 

그러나 DFS는 모든 경우의 수를 탐색한다. 다시 위의 예를 빌려, 132이라는 수를 탐색할 때, 십의 자리 수에 접근했을 때 원하는 수가 아님에도 불구하고 일의 자리 수까지, 즉 트리의 바닥에 도달할 때까지 탐색을 계속한다. 

 

n, m = map(int, input().split()) 
arr = [] # 프린트 할 결과 배열

def btrack():
    if len(arr) == m: # 배열 길이 초과하면 프린트하고, return 종료
        print(" ".join(map(str,arr)))
        return
    else:
        for i in range(1,n+1): # 1 ~ n까지 반복문 실행
            if i not in arr: # 중복되지 않으면
                arr.append(i) # 추가
                btrack() # 재귀로 호출해서 중복되지 않으면 추가, 아니면 지금까지 배열 프린트
                arr.pop() # 재귀 끝나면 여기로 돌아옴. 백트랙 > 이전 다시 탐색 
btrack()