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

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

---

흠...ㄷㄷ

아이디어는 생각했는데 구현이 잘안된다..

 

처음 생각한 아이디어는 각 숫자에 대해서 사용했는지 체크하고 재귀를 돌리는 것이었는데 잘 안되서 다른 방법을 사용하였다.

 

다음으로 생각한 아이디어는 list를 하나 만들어 방문한 숫자들을 append하는데 깊이가 증가할수록 구분할 수 있게 -1을 넣어줬다. 

반복문을 돌면서 list의 마지막 원소와 append하려는 원소가 같으면 append를 하지 않고 재귀도 돌리지 않는다.

for문이 끝나면 해당 깊이에서 append한 원소들을 제거한다.  

 

사실 처음 생각한 아이디어가 더 쉬운 방법인데 시간만 날렸...

다른사람의 정답을 본 결과 for문을 돌리기 전에 used라는 리스트를 만들어주고 방문하지않고 사용되지 않았을때 

used에 해당 숫자에 대해 표시(True)를 해주고 재귀를 돌린다.

used는 함수에서 만들어주기 때문에 재귀를 돌릴때마다 다시 새로 만들어 지기 때문에 중복을 확인 할 수 있는것이다.

---

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

def Dfs(depth):
    if depth == m:
        print(' '.join(map(str, solve)))
        return
    used = [False for _ in range(max(my_list) + 1)]
    for i in range(n):
        if visited[i] == 0 and not used[my_list[i]]:
            used[my_list[i]] = True
            solve.append(my_list[i])
            visited[i] = my_list[i]
            Dfs(depth + 1)
            visited[i] = 0
            solve.pop()

def Dfs2(depth):
    if depth == m:
        print(' '.join(map(str, solve)))
        return
    append_count = 0
    double_check.append(-1)#depth 경계
    for i in range(n):
        if visited[i] == 0:
            if double_check[len(double_check) - 1] != my_list[i]:
                double_check.append((my_list[i]))
                append_count += 1
                solve.append(my_list[i])
                visited[i] = my_list[i]
                Dfs2(depth + 1)
                visited[i] = 0
                solve.pop()
    for j in range(append_count + 1):
        double_check.pop()



Dfs2(0)