[백준] 15649번 N과 M(1)

 

www.acmicpc.net/problem/15649

15649번: N과 M (1)

문제

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

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

 

입력

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

 

출력

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

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

 

풀이

DFS, BFS를 이용하여 가장 기본적으로 구현하는 순열을 구하는 문제이다.
전에 올린 itertools를 이용하면 쉽게 풀 수 있지만 재귀를 이용하여 구현하는 방법 역시 알고 있어야하기 때문에
2가지 방법으로 구현했다.

itertools permutations 이용

import itertools

N, M = map(int, input().split())

N = [i for i in range(1, N+1)]

answer = list(itertools.permutations(N,M))

for i in range(len(answer)) :
    for j in range(M) :
        print(answer[i][j],end = ' ')
    print()

input()을 이용하여 입력을 받고 itertools의 permutation 기능을 이용하여 구현하였다.

재귀함수 이용

import sys

N, M = map(int, sys.stdin.readline().split())
answer = []
check = [0 for _ in range(N)]

def NandM(index, N, M):
    if index == M :
        for i in range(M):
            print(answer[i] , end = ' ')
        print()
        return
    
    for i in range(N):
        if not check[i]:
            check[i] = 1
            answer.append(i+1)
            NandM(index+1, N, M)
            check[i] = 0			####
            answer.pop()
NandM(0, N, M)

전에 올린 sys를 이용하여 입력을 받았다.
check 리스트를 이용하여 중복으로 사용할 수 없게 확인한 뒤 중복이 아닌 경우에
list에 넣고 다시 NandM함수를 호출하는 재귀를 이용하여 구현하였다.

####로 표시한 NandM함수에서 빠져나온 뒤에는 마지막에 선택한 숫자를 제거하고 다음 숫자를 선택해야하기 때문에
pop한 뒤 check리스트의 해당 값을 0으로 바꿔 다음에 다시 사용할 수 있게 하였다.