[DFS기초] - 순열구하기

순열 구하기

 

1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑아일렬로나열하는방법을모두 출력합니다.

 

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제 1

3 2

▣ 출력예제 1

1 2
1 3
2 1

2 3

3 1

3 2

6

 

 

나의 코드

def DFS(L):
    global cnt
    if L==m:
        cnt+=1
        print(ch)
    else:

        for i in range(1,n+1):
            for j in range(L):
                if ch[j]==i:
                    break
            else:
                ch[L]=i
                DFS(L+1)
          

n,m=map(int,input().split())
ch=[0]*m
cnt=0
DFS(0)

print(cnt)

 

꽤나 시간이 걸렸다..!

결론적으로 중복순열과 같은 코드에서 이전의 체크 리스트에 해당 입력할 i가 있는지 확인하는 코드를 추가해서 구현 !

 

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
def DFS(L):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                DFS(L+1)
                ch[i]=0

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*m
    ch=[0]*(n+1)
    cnt=0
    DFS(0)
    print(cnt)

나의 코드와는 약간 다르게 체크 리스트를 추가하여 구현하였다.