알고리즘 백준 15649 N과M(1)(파이썬)

알고리즘 백준 15649 N과M(1)(파이썬)

백준 파이썬 N과M(1)

백준 N과M(1) 파이썬

 

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

코드

def backtracking():                             
    if len(treeList) == M:       #1)
        printList.append(copy.deepcopy(treeList))  #1-1)
       # return printList1


    for i in range(1,N+1):   #2)
        if i in treeList:
            continue
            
            
        treeList.append(i)
        backtracking()
        treeList.pop()




def printResult(L):  #3)
    for j in L:
        j = map(str,j)
        print(" ".join(j))




if __name__ == '__main__':
    import sys
    import copy

    N, M = map(int, sys.stdin.readline().split())  # N,M받기
    printList=[]  #출력값이 들어있는 리스트
    treeList=[]   # 스택을 위한 리스트
    backtracking()
    printResult(printList)

 

 

코드설명

0-1) 백트래킹 문제의 기초 문제로서 백트래킹은 재귀랑 스택을 통해 모든 경우의 수를 탐색하는 중에 필요 없는 경우의 수를 가지치기를 통해 경우의 수를 줄여 효율적으로 탐색하는 방법이다.

 

0-2) 해당 문제에서는 가지치기를 해당 원소가 스택에 있을경우에 그와 관련된 경우의 수를 탐색하지 않는 방법으로 구현을 하였다.

 

1) 해당 부분은 스택인 (treeList) 부분이 입력받은 출력값의(M)의 길이와 같다면 출력리스트(printList)에 추가하는 부분이다.

 

1-1) 해당 부분은 처음에는 그냥 printList.append(treeList)로 구현을 하였는데 treeList를 pop할시 printList에서도 pop이 적용되어 데이터가 소실되므로 deepcopy를 통해 데이터 손실을 방지하였다 - 해당 부분은 파이썬의 얉은 복사, 깊은 복사 부분이며 해당 부분은 다시 정리하도록 하겠다.

 

 

2) 1부터 입력받은(N)까지 돌며 스택에 해당 값이 있을때(가지치기를 해야하는경우)에는 해당 값과 관련된 경우의 수를 건너뛰며 

스택에 해당 값이 없을 경우에는 스택에 추가하고 재귀를 통해 다른 경우의 수를 탐색한다.

탐색이 끝난(스택의 길이가 M과 같을때) 부분은 pop을 통해 제거하며 다른 경우의 수를 계속 탐색한다.

 

 

3) 탐색을 통해 얻은 printList를 출력값에서 원하는대로 출력한다.!

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main