백준 파이썬 15663번 N과 M (9) (Today I Learn 2025.09.19)

백준 파이썬 공부 2025.09.19
15663번 N과 M (9) (실버 2)

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

- N개의 자연수 중에서 M개를 고른 수열

2. 입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 
입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

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

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

4. 문제 풀이
n과 m 1번 문제에서, n의 수를 지정하고, n의 수들이 중복이 가능하도록 한 문제
굉장히 다양한 시도를 해봤다.
각각의 값과 개수를 저장해서 카운팅을 해봤지만, 너무 복잡해져 다른 방법이 있을것이라 추측

해당 깊이의 값이 중복되지 않으면 된다는 것을 알았다.
예를 들어
[1, 2, 3, 3] 리스트에서 m = 3인 순열을 순서대로 뽑는다면,
1 2 3(index = 2)
1 2 3(index = 3)
>> 이렇게 중복이 일어날 수 있기에
같은 깊이의 위치에서 같은 값이면 저장이 되지 않도록
이전에 쓰인 값을 저장하여 검사를 시행해줬다 

>> 코드

n, m = map(int, input().split())
num = list(map(int, input().split()))
num.sort()

visited = [False] * n
answer = []
answer_list = []

def DFS9(depth):
    if depth == m:
        answer_list.append(answer[:])  # 깊은 복사
        return
    
    prev = -1  # 같은 깊이에서 이전에 쓴 값
    for i in range(n):
        # 해당 위치의 값을 쓰지 않았으며, 해당 깊이에서 이전에 쓴 값과 다른 경우
        # 다른 인덱스의 같은 값을 쓰지 않기위해 해당 깊이에 쓰인 값 검사
        if not visited[i] and prev != num[i]:
            visited[i] = True
            answer.append(num[i])
            DFS9(depth+1)
            answer.pop()
            visited[i] = False
            # 해당 깊이의 값 저장
            prev = num[i]

DFS9(0)

# 출력
for arr in answer_list:
    print(*arr)

5. 문제 링크
https://www.acmicpc.net/problem/15663