[백준/Python] 10974번: 모든 순열

문제

 

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

---

Algorithm

 

• 깊이 우선 탐색(DFS)과 백트래킹을 이용하여 모든 가능한 조합을 탐색한다.
• 현재까지의 순열을 temp 리스트에 저장한다.
• 모든 숫자를 하나씩 시도하며, 이미 사용된 숫자는 제외한다.
• 순열이 완성되면 출력하고, 다른 가능한 순열을 찾기 위해 마지막 숫자를 제거한다(백트래킹).

 

 

---

 

 

Code

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

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

dfs()