[백준] 15649 - N과 M (1) 분류 (파이썬)

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

15649번: N과 M (1)

문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

 

 

접근방법

수열을 만드는 방법을 생각해보자.

(1~N 사이의) 숫자 하나를 골랐다면, 해당 숫자를 제외하고 N-1개 중 하나를 구하고, 이러한 과정을 M번 반복하여 수열 하나를 만들 수 있다.

반복되는 부분은 쉽게 찾을 수 있다. 위의 밑줄 부분을 함수화 시켜보자.

1. 순차적으로 숫자를 하나 고름
2. 해당 숫자를 제외하고 숫자를 고름 M-1번 (1번의 경우 제외)

공통분모는 숫자를 고른다는 부분이다. 그럼 처음에 순차적으로 함수를 호출하고, 함수 내부에서 횟수를 확인하며 계속 반복시킬 수 있지 않은가?

그렇다 재귀 함수를 사용했다.

 

재귀 함수 이용 

나는 재귀 함수를 쓸 때, 항상 먼저 생각하는 것이 종결 조건이다. 종결 조건까지만 제대로 가도 디버깅으로 눌러보면서 틀린 부분 수정까지 하기가 편하다.  다음과 같은 방식으로 나는 재귀 함수를 짠다. 맞는 방법인지는 모르겠으나, 재귀가 어렵다면 이 방법도 한번 참고하면 좋을 것 같다.

 

1. 종결 조건을 코딩하고 끝날 때, 결과 형식을 생각한다. return을 통해 넘길 것인지, 그대로 출력할 것인지 등 
2. 반복되는 부분을 코딩한다.
3. 루프가 발생하지 않도록 조건을 만들고 호출한다. 이때 매개변수가 필요하다면, 추가하면서 수정한다.

 

 

코드

def dfs(N, M, num_set, ref=""):
    data = ref
    #1번 부분
    if M ==0:
        print(data)
        return
    else:
        #2번 부분
        for i in range(1, N+1):
            # 이미 사용되었다면 continue
            if num_set[i-1] == True:
                continue
            num_set[i-1] =True
            #3번 부분
            nx_data= data + str(i) + " "
            dfs(N,M-1,num_set,nx_data)
            #사용 후 원복
            num_set[i-1] =False


def solution(N, M):
    answer = 0
    # N만큼 배열을 만들어 사용
    num_set = [False] * N
    dfs(N, M, num_set)

    return answer

def output():
    N, M = map(int, input().split())
    solution(N, M)
    return 0


output()