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

문제)

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

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

 

입력)

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

 

출력)

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

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

---

#dfs
N, M = map(int, input().split())
arr = list(range(1, N + 1))

def solution(n, arr, R):
    # 마지막 층에 도착했을 경우 2중 리스트에서 값을 꺼내고 출력
    if n == 1:
        print(' '.join([str(i) for i in R[0]]))
    else:
        # 시작값에서 끝값까지 하나씩 끝까지 찾아가서 출력 후 다음 값으로 넘어감
        for r in R:
            for i in arr:
                # copy를 안할 경우 원본이 변경되어 출력이 이상해짐
                tmp = r.copy()
                if i not in tmp: 
                    tmp.append(i)
                    # 재귀 호출할 때 tmp를 감싸 주지않으면 정수데이터가 넘어가져서 오류 발생
                    solution(n - 1, arr, [tmp])
if M == 1:
    for i in arr: print(i)
else: solution(M, arr, [[i] for i in arr])

풀이 : 

 이번 문제를 해결할 때 깊이 우선 탐색(dfs, Depth-First Search)알고리즘을 사용해 보았다. 입력이 (N, M) = (4, 4)일 때 아래 그림과 같이 진행된다.

[그림 1] 단계별 출력까지의 과정

 한 단계 깊어질 때마다 solution함수를 재귀함수로 사용하여 최종 단계까지 도착한 뒤 출력하고나서 그 다음 숫자로 넘어가게 된다.