📌난이도🥈3

📌코드

1)

from collections import deque
N, M = map(int, input().split())
stack = deque()


def tracking():
    if len(stack) == M:
        for i in stack:
            print(i, end=' ')
        print()
        return

    for i in range(1, N+1):
        if i in stack:
            continue
        stack.append(i)
        tracking()  # 2, 3, 4 번째로 들어감
        stack.pop()  # 재귀 이후라 들어간 만큼 pop()함

tracking():

2)

from collections import deque
N, M = map(int, input().split())
visited = [False]*(N+1)
stack = deque()


def tracking():

    if len(stack) == M:
        for i in stack:
            print(i, end=' ')
        print()
        return

    # 1, 2, 3, 4 넣는 것
    for i in range(1, N+1):
        if visited[i]:
            continue
        stack.append(i)
        visited[i] = True
        tracking()  # 2 ,3 ,4 번으로 들어가는 재귀
        stack.pop()
        visited[i] = False
   
   tracking()

📌후기

백트래킹 첫 문제인데 접근 방식이 매우 좌절스러웠다.

접근

백트래킹 = dfs + 가지치기조건 추가라고 해서
stack을 써야할 것 같았다.

• len(stack) = M 일때 출력
• 재귀를 통해서 2번쨰, 3번쨰, 4번쨰 요소 추가

하지만 요소 삭제하는 것이 어려웠다.

나는 출력하는 부분( len(stack) = M ) 에서 pop하려고 했었다. 재귀의 되돌아오는 성질 을 생각하지 않아서 오래걸렸던 것 같다.