[백준/BOJ] - 11974번 python 풀이 - 백트래킹

---

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

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

---

dfs를 활용한 백트래킹 기법을 활용한 문제.

temp의 길이가 n일 경우 출력하기 때문에 출력하고 return 하게끔 구현한다.

재귀함수에서 temp에 i값이 존재하는지 확인하며 없을 경우 추가하고

재귀함수로 들어간다.

dfs() 줄 다음의 temp.pop()에 도달하는 경우는 이미 출력을 끝냈다는 의미이므로

맨 끝 값을 제거하고 해당 재귀 함수에서 반복문을 더이상 진행할 수 없을 경우 재귀함수 종료가 되어

이 전의 재귀함수로 돌아간다. 앞서 언급했던 내용의 반복을 통해 값이 겹치치 않는 집합을 얻을 수 있다.