[백준] 15655번(python 파이썬)

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

---

N과 M 5의 확장 문제 이다.

입력으로 n개의 숫자를 임의로 받는다.

이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다.

이전 방문 노드보다 큰 숫자를 append한다.

반복문의 i를 solve 리스트에 append, pop 하는 것이 아닌 오름차순으로 정렬한 리스트의 i번째 값을 append, pop 한다.

 

사실 visited를 써서 풀었는데 visited는 없어도 된다. 

if depth == 0 or solve[depth - 1] < my_list[i]  여기서 이전 노드보다 작은 노드들은 걸러지기 떄문이다.

 

visited를 써야하는 경우는 이전노드들만 방문처리 되고 다른 노드들은 탐색할 경우이다.

 

---

n, m = map(int, input().split())
my_list = list(map(int, input().split()))
my_list.sort()
visited = [False] * n
solve = []

def Dfs(depth):
    if m == depth:
        print(' '.join(map(str, solve)))
        return

    for i in range(n):
        if not visited[i]:
            if depth == 0 or solve[depth - 1] < my_list[i]:
                solve.append(my_list[i])
                visited[i] = True
                Dfs(depth + 1)
                visited[i] = False
                solve.pop()

Dfs(0)