백준 15649번: N과 M (1) (S3) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/15649

자연수 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

문제 요약) 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력해라. 오름차순으로.

풀이 과정

1~N까지 수 중에 M개를 고른 수열을 찾아야 합니다. 가장 왼쪽 자리부터 자릿수를 하나씩 증가시키면서 숫자를 채우고 길이가 M이 되면 숫자(수열)를 출력하고, 그 전 단계(한 칸 전의 자릿수)로 돌아가서 다른 선택을 해야 합니다. 즉, 백트래킹 알고리즘으로 해결할 수 있는 문제입니다.

백트래킹은 재귀로 구현할 수 있습니다. 재귀 종료 조건은 채운 숫자의 길이가 M이 될 때로 설정하고, 이때 해당 숫자를 출력합니다.

종료 조건에 해당하지 않을 때에는 숫자를 채워야 합니다. 숫자를 담을 배열을 두고, ‘중복 없이’ M개를 고르는 것이기 때문에 이전에 고른 숫자 중에 i가 없을 때에만 배열에 i를 추가합니다. 그 후 재귀적으로 함수를 호출해서 이후의 자릿수를 계속 채워나갑니다. 종료 조건을 만족할 때까지.

종료 조건을 만족하면 재귀 함수를 호출했던 코드 바로 아랫줄부터 시작됩니다. 이때 전 단계 즉, 한 칸 전의 자릿수로 돌아가기 위해 배열의 맨 뒷자리의 수를 제거합니다. 이때 pop을 사용했습니다.

정답 코드

N, M = map(int, input().split())
arr = []

# 백트래킹을 통한 M 자릿수 수열 찾기
def backtracking():
    # 현재 숫자가 M개면 출력하고 재귀 종료
    if len(arr) == M:
        # M 자리의 수열을 공백으로 구분해서 출력
        for i in range(M):
            print(arr[i], end=' ')
        print()
        return
    # i에 1부터 N까지 넣어가며 반복
    for i in range(1, N+1):
        # i가 배열에 존재하지 않으면 (= 이전에 추가된 적 없는 숫자이면)
        if arr.count(i) == 0:
            # 배열에 추가
            arr.append(i)
            # 다음 자릿수를 보기 위해 재귀 호출
            backtracking()
            # 재귀가 종료되면 여기부터 실행되고,
            # 이때 전 단계(= 한 칸 전의 자릿수)로 돌아가기 위해 맨 뒷자리 수를 제거
            arr.pop()
            
# 백트래킹 시작
backtracking()

이상입니다.