[백준] 15663번: N과 M (9) - python

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

15663번: N과 M (9)

 

아이디어

 

처음 뿌리를 뻗을때 중복을 제거한 다음 뿌리를 펼칠 생각

그러나 출력은 아래처럼 나와야되지만 내 코드는

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

같은 경우의 케이스가 출력이 불가능했다.

1 7
1 9
7 1
7 9
9 1
9 7

 

문제의 코드

 

 DFS(L):
    if L == m:
        for i in range(m):
            print(res[i], end=' ')
        print()
    else:
        for i in range(len(s)):
            if ch[i] == 0:
                ch[i] = 1
                res[L] = s[i]
                DFS(L+1)
                ch[i] = 0


n, m = map(int, input().split())
arr = list(map(int, input().split()))
s = set(arr)
s = list(s)
res = [0] * m
ch = [0] * (n+1)
s.sort()
DFS(0)

 

그냥 간단히 상태트리를 생성 후 더 들어갈때 값을 저장하는 아이디어

 

생각 후 간단히 저장변수에 갱신을 하면서 똑같은 값이 여러번 안나오게 설정을 해줬다.

 

def DFS(L):
    if L == m:
        for i in range(m):
            print(res[i], end=' ')
        print()
    else:
        remember = 0
        for i in range(n):
            if ch[i] == 0 and remember!=arr[i]:
                ch[i] = 1
                res[L] = arr[i]
                remember = arr[i]
                DFS(L+1)
                ch[i] = 0
        


n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
res = [0] * (m+1)
ch = [0] * (n+1)
DFS(0)

 

완성