[인프런] 순열 구하기

---

문제설명

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

입력조건

• 첫줄에 자연수 N (3 <= N <= 10)과 M(2 <= M <= N)이 주어진다.

출력조건

• 첫줄에 결과를 출력한다. 맨 마지막에는 총 경우의 수를 출력한다.
• 출력순서는 사전순으로 오름차순으로 출력한다.

사고과정

• 처음에 상태트리를 두 갈래로 만들려 했다가 애를 먹었다.. 중복이 없이 뽑아야 해서 두 갈래로 만들어야 하는 줄 알았는데, 중복순열 때 처럼 여러 갈래길로 만들어야 한다. 단, 중복을 허용하지 않기 때문에 중복 순열처럼 구현하되, 방문 체크용 리스트를 하나 만들어서 DFS 탐색 함수 안에 조건을 추가해주어야 한다!
• 이번 문제를 계기로 정리가 된게.. 중복을 허용하지 않을 때는 무조건 방문 여부 체크용 리스트를(1차원이던 2차원이던) 무조건 정의하고 들어가야한다고 생각해야겠다..!

풀이(스스로 못 푼 풀이)

n, m = map(int, input().split())
res = [0] * m
# 중복허용 안되니까 방문했는지 여부 체크하는 체크 리스트 정의해야함!
check = [0] * (n+1)
cnt = 0

def dfs(idx):
    global cnt
    if idx == m:
        for r in res:
            print(r, end=' ')
        print()
        cnt += 1
    else:
        for i in range(1, n+1):
            if check[i] == 0:
                check[i] = 1
                res[idx] = i
                dfs(idx+1)
                check[i] = 0  # 체크풀어줘서 다른 원소 탐색할 기회 부여!

dfs(0)
print(cnt)