10974

날짜 : 2022. 12. 07

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10 ** 9)

n = int(sys.stdin.readline())
stack = []

def dfs():
    if len(stack) == n:
        print(*stack)  # 수열 완성 후 출력
        return
    for i in range(1, n+1):  # 1부터 시작
        if i not in stack:  # 수열 리스트에 없는 경우
            stack.append(i)  # 넣기
            dfs()
            stack.pop()

dfs()

 

 

풀이

- DFS를 활용해서 오름차순으로 for문을 돌리고 스택에 숫자가 없는 경우 넣은 후 재귀하는 방식으로 문제를 풀이했다.

(백트래킹)

 

 

알게된 점

- 오랜만에 백트래킹 문제를 풀어서 좀 어색했다.

- pypy로 해서 계속 메모리 초과가 떴는데 python3로 하니까 곧바로 풀렸다.

 

 

참고 사이트

- https://honggom.tistory.com/115

[백준] 10974번 문제 (모든 순열) 파이썬(Python) 풀이