15649 N과M(1) _python

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

12개의 비슷한 문제가 있는 문제 (1)~(12)

 

 

문제 접근

백트래킹 문제다.

문제를 읽어보면 끝자리를 계속 바꿔나가니 스택으로 접근하기 가장 알맞아보인다.

스택으로 접근하는데 모든경우를 탐색한다는 것은 dfs를 사용하면 쉽게 풀린다.

 

문제를 풀면서 적어둔 주석

"""

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

dfs -> for문을 한번 반복시킴.

dfs횟수 -> 배열의 길이만큼 반복(M만큼)

"""

 

 

코드

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
arr = []
visited = [False] *(N+1)

def dfs():
    if len(arr)==M:
        print(*arr)
        return
    for i in range(1,N+1):
        if not visited[i]:
            visited[i] = True
            arr.append(i)
            dfs()
            arr.pop()
            visited[i] = False

dfs()

visited를 만들지 않고 if i not in arr을 해도 풀릴것이다