Koala - 16기/코딩테스트 기초 스터디

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

joo-nick 2024. 11. 25. 00:22

문제

 

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()