[BOJ][python] 15663. N과 M (9)

 

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

15663번: N과 M (9)

---

💡IDEA

재귀와 DFS를 사용하는 문제이다.

조건을 만족하는 수열을 출력하기 위해서 요소의 방문을 확인할 배열 하나, 중복된 수열을 출력하는 것을 방지할 상수 하나가 필요하다.

중복 수열 제거용 상수는 깊이가 다를 때마다 초기화 해주어야 한다.

방문 확인 및 이전에 쓰인 요소 값과 같은지 확인해주며 DFS를 수행한다.

📌CODE

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
numbers = sorted(list(map(int, input().split())))

v = [0]*N
ans = []
def permutation(idx):
    if idx == M:
        print(*ans)
        return
    tmp = 0
    for i in range(N):
        if not v[i] and tmp != numbers[i]:
            v[i] = 1
            ans.append(numbers[i])
            tmp = numbers[i]
            permutation(idx+1)
            v[i] = 0
            ans.pop()

permutation(0)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
numbers = sorted(list(map(int, input().split())))

def permutate(idx, perm, sel):
    if idx == M:
        print(*perm)
        return
    tmp = 0
    for i in range(N):
        if not sel[i] and tmp != numbers[i]:
            sel[i] = 1
            perm.append(numbers[i])
            tmp = numbers[i]
            permutate(idx+1, perm, sel)
            sel[i] = 0
            perm.pop()
            
permutate(0, [], [0]*N)