[백준] 15663번 - Silver 3 N과 M (9), 파이썬 코드

solved.ac의 Class 4 문제 중 N과 M(4) 문제이다.

1부터 비내림차순으로 내려가야 하는 특징 때문에 재귀 DFS 문제라는 것을 알 수 있다.

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

 

해결했던 코드는 다음과 같다.

import sys
global n, m

numbers = []
lst = []
visited = []

def dfs():
    before = 0
    if len(lst) == m:
        print(*lst)
        return
    for i in range(n):
        if before != numbers[i] and not visited[i]:
            lst.append(numbers[i]); visited[i] = True
            before = numbers[i]
            dfs()
            lst.pop(); visited[i] = False


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    numbers = sorted(list(map(int, sys.stdin.readline().split())))
    visited = [False for i in range(n)]
    dfs()