[python_파이썬_Pass]백준_15651번_N과 M(3)_백트래킹_풀이

공부하는허딩크 : https://www.youtube.com/live/Q8BKRFH8mW0?feature=shared

백트레킹 문제를 1번과 2번을 통해서 itertools를 활용해서 해결하는 방법과 재귀함수를 활용해서 해결하는 방법을 복습하면서 정리했다.

1. itertools.permutations()와 재귀 활용 : https://heodinkcodingdiary.tistory.com/88

[python_파이썬_Half Pass]백준_15649번_N과 M(1)_백트래킹_풀이

2. itertools.combinations()와 재귀 활용 : https://heodinkcodingdiary.tistory.com/89

[python_파이썬_Half Pass]백준_15650번_N과 M(2)_백트래킹_풀이

 

이번 문제는 (1)과 (2)의 문제와는 다르게 중복이 허용된다는 점이다. ex. (1, 1) (2, 2)등

 

<첫번째 시도 : itertools활용>

from itertools import product as pr 이런식으로 사용가능하다.

product는 permutaions()보다 중복이 허용된다.

permutations() + 중복불가 vs product() + 중복허용 ※단, product(list, repeat = num) repeat을 활용한 조건을 줘야한다.

combinations() + 중복불가 vs combinations_with_replacement() + 중복허용

"""itertools활용 : product(list, repeat = 조건)"""

import sys

import itertools

input = sys.stdin.readline

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

nums = list(i for i in itertools.product(range(1, N + 1), repeat = M))

for i in nums:

    print(*i)

 

<두번째 시도 : 재귀함수 활용>

(1)과 (2)의 문제 복습을 통해 어느정도 감을 잡았다.

"""backtracking활용"""

import sys

input = sys.stdin.readline

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

def product(seq):

    if len(seq) == M:

        print(*seq)

        return

   

    for i in range(1, N + 1):

        product(seq + [i])

       

product([])

 

<다른사람 풀이 참고 : depth활용>

이것도 좋은 아이디어인듯하다.

"""depth 활용"""

import sys

input = sys.stdin.readline

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

answer = []

def product(depth):

    if depth == M:

        print(*answer)

        return

   

    for i in range(1, N + 1):

        answer.append(i)

        product(depth + 1)

        answer.pop()

   

product(0)