[백준] 10974. 모든 순열 : python

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

10974번: 모든 순열

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

---

 

풀이

부르트보스로 풀이를 하고자 하였다.

틀린코드

다음과 같이 풀면 (내가 사용한 테스트케이스 내에서) 모든 순열이 출력이 되지만 사전순으로 출력이 되지 않아서 고생하다가 다른 사람의 풀이를 참고하여 풀었다

f arr(n):
    global ans
    if n == N:
        print(*visited)
    else:
        for i in range(N):
            if visited[i] == 0:
                visited[i] = n+1
                arr(n+1)
                visited[i] = 0

N = int(input())
visited = [0] * N
ans = []
arr(0)

맞은코드

def arr(depth):
    global ans

    if depth == n:
        print(*visited)
    else:
        for i in range(n):
            if i + 1 in visited:
                continue
            visited[depth] = i + 1
            arr(depth + 1)
            visited[depth] = 0
n = int(input())
visited = [0] * n
arr(0)

0일때가 아닌 존재하지 않을때, 그리고 index값을 depth 값으로 받아와야했다