[Baekjoon] 15649 N과 M(1) - Python

풀이

dfs로 구현

dfs는 stack , bfs는 queue!

입력

중복된 값을 입력하지 못하므로 visited 리스트 생성

dfs

for문을 돌며, 만약 방문을 안한 number라면
방문처리를 해주고, stack에 append()해준 뒤
dfs()재귀함수를 호출한다.

또 dfs()안에서는 만약 stack의 값이 M과 같다면
stack 값을 프린트 해주고 return된다.

(len(stack) == M)되었다고 가정했을 때
dfs함수가 return되므로 끝난다.

visited[number] = False구간으로 이동된다.
stack이 빠지고 난 뒤 정상적으로 stack에 쌓이기 위해
false처리가 되고
stack.pop()이 실행된다.

import sys 
input = sys.stdin.readline

N, M = map(int, input().split())
visited = [False for _ in range(N+1)]
stack = []

def dfs():
    if len(stack) == M:
        print(*stack)
        return 

    for number in range(1,N+1): 
        if not visited[number]:
            visited[number] = True
            stack.append(number)
            dfs()
            visited[number] = False 
            stack.pop() 


dfs()