순열 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

▣ 입력설명

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

 

▣ 출력설명

첫 번째 줄에 결과를 출력합니다.

맨 마지막 총 경우의 수를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제

3 2

 

▣ 출력예제

1 2

1 3

2 1

2 3

3 1

3 2

6

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

def DFS(v):
    global cnt
    #두개 다 뽑은 경우
    if v == M:
        for x in lst:
            print(x, end = ' ')
        print()
        cnt += 1
    #아직 다 안뽑음
    else:
        for i in range(1,N+1):
            #ch[i]가 1이면 i를 이미 뽑은것, 넘어가야함
            if ch[i] == 1:
                continue
            #i 아직 안뽑음
            else:
                #i뽑고
                lst[v] = i
                #i뽑았음을 체크
                ch[i] = 1
                #i뽑은 상태로 다음거 뽑으러 가기
                DFS(v+1)
                #i 뽑았음 체크 해제
                ch[i] = 0

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

 

모범답안

#모범답안
def DFS(L):
    global cnt
    if L == m:
        for j in range(m):
            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())
    res = [0]*m
    ch = [0]*(n+1)
    cnt = 0
    DFS(0)
    print(cnt)

 

느낀점

1. 수월하게 해결했다! 원래 반복문 돌 때 이미 lst 에 있으면 continue하는 방식으로
하려고 했는데.. ch리스트를 만들어서 뽑았는지 안뽑았는지를 1과 0으로 구분해 
체크하는것이 참 좋은 방법인것같다!

2. DFS에 대해 알아가는것같다.. 매개변수로는 트리의 레벨을 넣고, 
if-else문으로 탐색을 종료하는 지점을 if에 넣고 else에는 탐색을 계속하는 문을 넣고..
가지 수가 늘어나면 그건 반복문으로 해결!
이게 기본 아이디어인것같다. 물론 문제마다 조금씩 변화를 줘서 해결해야하지만!!
잘하구이땅!

3. DFS(levle+1) 윗 부분은 호출 전에 처리하는 부분!
아랫 부분은 되돌아온 이후니까 처리한걸 풀어줘야 함
새로운 가지로 뻗어야 하니까 이전 가지를 위한 처리를 없애주기!
이것도 기본 아이디어! 

 

---

 

다시 풀어보기

#다시 풀어보기
def DFS(v):
    global cnt
    if v == M:
        for x in result:
            print(x, end=' ')
        print()
        cnt+=1
    else:
        for i in range(1,N+1):
            if ch[i] == 0:
                result[v] = i
                ch[i] = 1
                DFS(v+1)
                ch[i] = 0

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