[실버 3] 15649번: N과 M (1)

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

15649번: N과 M (1)

---

문제

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

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

입력

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

출력

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

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

---

사고의 흐름

• 순열이니까 원래대로라면 itertools 라이브러리를 쓰겠지만, 지금은 Backtracking을 연습 중이니까 재귀 함수로 코드를 작성해보자.
• 중복을 허용하지 않고 선택하려면 그냥 BFS 돌릴 때처럼 별도로 bool 타입 List를 만들면 되는구나.

내가 작성한 소스코드

import sys
r = sys.stdin.readline


def print_seqs(n, m, seq, visited, depth):
    if depth == m:
        for v in seq:
            print(v, end=" ")
        print()
        return

    for i in range(n):
        if visited[i+1] == True:
            continue
        
        seq.append(i+1)
        visited[i+1] = True
        print_seqs(n, m, seq, visited, depth+1)
        del seq[-1]
        visited[i+1] = False


n, m = map(int, r().split())
visited = [False] * (n+1)
print_seqs(n, m, [], visited, 0)

남이 작성한 소스코드

BaaaaaaaarkingDog 님:
https://blog.encrypted.gg/945

피드백

• 조건에 따라 List 내의 원소를 선택하려면 반복문 안에서 뭔가를 하려 하지 말고, bool 타입 List를 하나 만들어서 선택할지 말지를 결정하는 정보를 저장한다.