15650

날짜 : 2022. 10. 09

사용 언어 : python

 

문제

 

코드

import sys

def dfs():
    if len(s) >= 2 and s[-1] < s[-2]:
        return
    if len(s) == m: # 스택에 m개의 요소가 쌓이면 출력 후 리턴
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1):
        if visited[i]:
            continue
        visited[i] = True
        s.append(i)
        dfs() # 재귀적으로 실행
        s.pop() # 맨 뒤에것 삭제
        visited[i] = False
    return

n, m = map(int, sys.stdin.readline().split()) # n : 노드 개수, m : 깊이
s = [] # 출력할 스택
visited = [False] * (n+1) # 방문여부 표시
dfs()

# 출력할 스택과 방문여부 체크용 리스트 생성
# 재귀적으로 실행하면서 출력스택 용량이 다 차면 출력 후 해당 함수를 빠져나오면서 False로 다시 반환

 

 

알게된 점

- 백트래킹을 활용한 기본문제였다

- 백트래킹 과정에서 스택이 오름차순이 되지 않는 경우 곧바로 재귀함수를 탈출하는 조건문을 넣어 문제를 풀이했다.

 

 

참고 사이트

- https://zidarn87.tistory.com/331

파이썬 / BOJ 백준 / 15650번 N과 M(2) - 백트래킹