[백준] 15649번 N과 M (1)

[백준] 15649번 N과 M (1) - 파이썬

코딩 코딩 코오딩 2021. 5. 22. 23:36

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

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

import itertools
n, m = map(int,input().split())
num_list = [i for i in range(1,n+1)]

num=list(itertools.permutations(num_list,m))
for i in num:
    print(" ".join(map(str,i)))

이렇게 간단하게 파이썬으로는 해결이 가능하다

하지만 이건 내가 원하는 풀이가 아니다

이유는 백트래킹을 하나도 생각하지 않고 풀었기 때문

알고리즘을 공부하기 위해서는 생각하는 방법을 길러야하는 데

다른 풀이를 꼭 생각해야겠다.

import sys

n, m = map(int,sys.stdin.readline().split())

num_list = [i for i in range(1,n+1)]
num_list.sort()
answer = [0] * n
visited = [False]* n
def dfs(count):

    if count == m:
        for i in range(m):
            print(answer[i], end=" ")
        print()
        return

    for i in range(len(num_list)):
        if not visited[i]:
            visited[i] = True
            answer[count] = num_list[i]
            dfs(count+1)
            visited[i] = False

dfs(0)

백트래킹 풀이이다. 끝