백준 15649번 [Python] 문제풀이 (N과 M(1)) - 이정개

문제

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

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

 

 

입력

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

 

 

출력

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

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

 

 

예제 입력 1

3 1

 

 

예제 출력 1

1
2
3

 

 

알고리즘 분류

ㆍ백트레킹

 

 

파이썬 코드(백트래킹)

n, m = map(int, input().split())

number_list = [1 + i for i in range(n)]   # 숫자 리스트
check_number = [False] * n                # 중복숫자 체크
array = []                                # 출력할 수열
 
def DFS(x):
    if x == m:                            # 수열 m개를 충족할경우 출력
            print(*array)            
            return
            
    for i in range(n):
        if check_number[i]:               # 중복될 경우 패스
            continue

        array.append(number_list[i])      # 수열 추가
        check_number[i] = True            # 사용한 수 체크

        DFS(x + 1)                        # + 1번째 수열을 위해 재귀함수 호출

        array.pop()                       # 수열 마지막 자리 삭제
        check_number[i] = False           # 사용한 수 초기화
DFS(0)    

문제를 풀기 위해서는 백트래킹에 대한 이해가 필요했다.

백트래킹이란 정말 짧게 줄이자면

조건이 만족하는 모든 경우의 수를 찾는 것.

여기서 또 깊이우선탐색(DFS), 너비우선탐색(BFS), 최선우선탐색(Best First Search)등이 있으나 자세한건 모르겠고

나는 DFS를 사용했다.

DFS도 줄이자면 조건을 만족하는 경우의 수를 찾았다면,

조건을 만족하기 직전 상태로 되돌아가 다음 경우의 수를 찾는 방식.

위 알고리즘도 재귀적으로 함수를 호출하고

이후 제일 바닥에 있는 함수부터 차례차례 종료되면서 다음 수열을 완성한다.