[백준] 10974번

[백준] 10974번 모든 순열

📌순열이란?

서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택하거나 나열하는 것

_nP_r = ${n! \over (n-r)!}$

[문제]

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

[입력]

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

[출력]

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

---

n = int(input())
temp = []

def per():
    if len(temp) == n:
        print(*temp)
        return
    for i in range(1, n + 1):
        if i not in temp:
            temp.append(i)
            per()
            temp.pop()
per()

우선 n을 입력 받고 생성한 순열을 담아 출력할 리스트를 생성해줍니다.

그리고 함수를 생성합니다. 함수는 조건문을 통해서 리스트의 길이가 n과 같아지면 출력하도록합니다.

이제 반복문을 통해서 순열을 생성해줍니다. 범위는 1부터 n+1까지 반복하는데 , n이 3일 때를 예시로 들어 설명하겠습니다.

만약 리스트에 i가 없으면 리스트에 i를 담아줍니다.

n = 3

1)

i=1일때,

만약 리스트에 1이 없으면 리스트에 1을 담아줍니다.

➡️ i=1, temp=[1]

dfs()를 호출합니다.

1)-1

i = 1인 경우는 이미 리스트안에 존재합니다.

i=2

i=2는 리스트안에 존재하지 않습니다. 그래서 리스트에 담아주고 dfs()를 호출합니다.

1)-2

i=1, i=2인경우는 리스트에 존재해서 패스하고 i=3일 때는 없으니 리스트에 담아주고 dfs()를 호출합니다.

여기서 temp=[1, 2, 3]이고 if len(temp) == n:을 만족하기 때문에 리스트 값 [1, 2, 3]을 출력하고 return 합니다.

temp.pop()을 실행합니다. ➡️ temp = [1, 2]

여기서 호출된 dfs()는 i=3까지 반복해서 이 dfs()를 호출한 1)-1로 돌아갑니다.

i=2일때 dfs()로 돌아와서 temp.pop()을 합니다.

➡️ temp=[1]

다시 반복문을 진행해서 i=3인 경우를 보니 리스트에 3은 존재하지 않기 때문에 리스트에 담아줍니다.

temp=[1, 3]

그리고 dfs()를 호출합니다.

i=1은 있으니 넘어가고 i=2가 리스트안에 넣어줍니다.

[1, 3, 2]를 출력합니다.

다시 리턴되어 temp.pop()가 되어 [1, 3]이되고 i=3은 리스트에 있으니 반복문이 종료되어 이전 호출로 갑니다.

이러한 과정을 반복해서 모든 수열을 얻을 수 있습니다.