[Baekjoon] 15651번 : N과 M (3) (Python, 백트래킹)

[Baekjoon] 15651번 : N과 M (3) (Python, 백트래킹)

 

목차

 

 

 

 

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

15651번: N과 M (3)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 1516ms / 코드 길이 207B

 

본 문제는 N과 M 시리즈 - 백트래킹 문제다.
15649번 N과 M (1) : https://aigong.tistory.com/427
15650번 N과 M (2) : https://aigong.tistory.com/428
15651번 N과 M (3) : https://aigong.tistory.com/475
15652번 N과 M (4) : https://aigong.tistory.com/476
15654번 N과 M (5) : https://aigong.tistory.com/480
15655번 N과 M (6) : https://aigong.tistory.com/481
15656번 N과 M (7) : https://aigong.tistory.com/482
15657번 N과 M (8) : https://aigong.tistory.com/483
15663번 N과 M (9) : https://aigong.tistory.com/484
15664번 N과 M (10) : https://aigong.tistory.com/485
15665번 N과 M (11) : https://aigong.tistory.com/486
15666번 N과 M (12) : https://aigong.tistory.com/487

 

일반적으로 방문처리를 통해 방문하지 않은 곳에 대해서만 list를 처리하는 방향으로 진행하여 중복을 없애지만 본 문제에서는 중복이 허용되므로 그 항목을 제외하였다.

 

def dfs():
    if len(t) == m:
        print(' '.join(map(str, t)))
        return

    for i in range(1, n+1):
        t.append(i)
        dfs()
        t.pop()

n,m = map(int, input().split())
t = []
dfs()

 

방법 2 - 메모리 30840KB / 시간 1892ms / 코드 길이 118B

 

itertools.permuations는 중복되지 않은 정렬을 의미하지만 product는 중복이 허용되도록 한다.

내장함수를 활용한 방법

 

from itertools import product
n,m = map(int, input().split())
for x in product(range(1, n+1), repeat=m):
    print(*x)