[백준 파이썬 15649번]N과M★백트래킹★

백트래킹이란??

 

- 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행

- 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.

- DFS(깊이 우선 탐색) 기반

 

VER 1.0

import sys

def backtracking():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1):
        if visited[i] == True:
            continue
        visited[i] = True
        s.append(i)
        backtracking()
        s.pop()
        visited[i] = False


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

visited =[False for i in range(n+1)]

backtracking()

재귀함수와 CONTINUE문 , return 문을 적절한 위치에 사용하여 반환시키도록 한다.

 

 

VER2.0

 

import itertools
import sys

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

res = [i for i in range(1,n+1)]

array = itertools.permutations(res, m)
for i in array:
    for j in i:
        print(j , end = ' ')
    print()

array 안은 2차원 배열 ==> 2중 for문을 돌리자

 

itertools의 라이브러리에서 

 

permutations , combinations, combinations_with_replacement 

 

이 3가지의 라이브러리 확인해본다.

import itertools
import sys

n, m = map(int, sys.stdin.readline().split())
nums = [i for i in range(1, n+1)]

array = itertools.permutations(nums, m) #중복된 조합은 제외
#itertools의 permutations함수를 사용해서 풀이
#Permutations 는 배열에서 원하는 길이에 맞는 모든 조합을 구하는 함수이다.
for i in array:
    for j in i:
        print(j, end = ' ')
    print()
print('=======================')
array2 = itertools.combinations(nums,m) #중복된 조합 모두 포함

for i in array2:
    for j in i:
        print(j, end = ' ')
    print()
print('=======================')
array3 = itertools.combinations_with_replacement(nums,m)
#중복된 조합 모두 포함 , 1 1 / 2 2 등 본인의 조합도 포함하기
#(nums, m)
for i in array3:
    for j in i:
        print(j, end = ' ')
    print()