순열 구하기

문제

순열 구하기
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:
        for j in range(L):
            print(res[j], 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()) #n은 구슬에 적힌 번호 1부터 n까지
    res=[0]*n
    ch=[0]*(n+1)
    cnt=0
    DFS(0)
    print(cnt)

-ch 리스트

체크 리스트 

def DFS(L):

    else:

        for i in range(1, n+1):

            if ch[i]==0:

                    ~~

ch[i]==0일 때만 코드가 작동하도록 설계--> 이미 사용된 숫자가 또 포함되면 안되기 때문이다

 

ch 리스트는 함수가 끝나면 초기화 되어야 한다.

else:

        for i in range(1, n+1):

            if ch[i]==0:

                ch[i]=1

                res[L]=i

                DFS(L+1)

                ch[i]=0 #되돌아와서 초기화하는 코드

DFS(L+1)에서 L+1==m이면 함수가 끝난다. 따라서 다시 DFS(L)로 돌아오고 ch[i]=0 코드를 통해

다시 초기화된다.

 

-result 리스트

말 그대로 결과값을 넣는 리스트이다.

def DFS(L):

  else:

        for i in range(1, n+1):

            ~~(생략)

                res[L]=i

                ~~~('')

DFS(L)에서 L은 순서, 계층을 의미한다. 결과값 리스트나 어떤 값이 아닌 것이다.

따라서 res[L]=i로 지정하는 것은 res리스트의 L번째 값에 1부터 n+1까지 모두 지정해서 결과값을

도출하는 것이다. ch[i]=1인 경우를 제외하고!

 

-res n개의 원소 VS ch (n+1)개의 원소

res는 그냥 결과값이므로 0번째부터 count해서 도출하면 되지만 ch리스트는 원소의 순서가 곧

구슬 번호이기 때문에 n+1개를 설정해야 한다. 예를 들어 ch[2]==1인 경우 2번 구슬이 이미 쓰였다는 뜻이다