[Python]백준 15649 - N과 M(1)

백준 15649-N과 M(1)

문제

코드

import sys
from collections import deque
input= sys.stdin.readline

def backtracking(cnt):
    if(cnt==M):
        print(' '.join(map(str, dq)))
    for i in range(1, N+1):
        if(visited[i] == False):
            dq.append(i)
            visited[i] = True
            backtracking(cnt+1)
            dq.pop()
            visited[i] = False

N, M = list(map(int, input().split()))

dq=deque()
visited = [False] * (N+1)
backtracking(0)

해설

백트래킹을 이용하여 문제를 풀었다.

입력: N, M = list(map(int, input().split()))

백트래킹:
백트래킹은 재귀의 방식을 이용한다.
cnt가 M이 되면 출력한다.
visited[i] 가 False 라면 즉, i가 dq에 있지 않다면 dq에 i를 넣고 visited[i]를 True로 바꿔준다.
backtracking(cnt+1)을 호출한다.
그후 dp에서 ifmf pop해준 다음 다시 visited[i]=False 로 해준다.

출력: print(' '.join(map(str, dq)))를 이용해 일렬로 출력해주었다.