[ 백준 ] 15652번 : N과 M (4) (파이썬)

문제 )

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

15652번: N과 M (4)

 

[ 풀이 ]

Backtracking Algorithm을 사용하여 문제를 풀어주었다 

 

- Backtracking Algorithm 이란? 

✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법
✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 
     유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다

 

- Node가 Promising한지 점검하는 법 

✔ 수열이 비내림차순이어야한다  (길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족)

 

 

< promising Function >

수열 list s의 원소들이 비내림차순이기 위해서 s의 원소들을 index=0~M까지 유망성 검사를 할 때, 그 전 index의 원소보다는 항상 크거나 같아야한다. 

예를들어, s[0]=2라면 s[1]은 2보다는 작으면 안된다. 
그러므로 Promising Function은 s[n-1]<=s[n]이면 True, s[n-1]>s[n]이면 False를 return한다. 

 

 

< findseq Function의 Algorithm >

✔ 초기화 된 수열 → s
✔ 수열의 index에 접근하는 변수 → n (0부터 M까지)

 

If list s에 M자리까지 숫자가 중복없이 채워진 경우 (수열이 완성된 경우)
           1. 수열 s를 출력
Else
           1. 값을 하나씩 늘려가는 index → i (1~N+1)
                     →  s[n]에 i값을 넣어준다
                     If i값이 중복되지 않고 오름차순인 경우 (promising function)
                                 Ⅰ. index=n+1에 대해 find function시행 

 

 

- python code 

def promising(num):
    if num!=0:
        if s[num-1]>s[num]:
            return False
    return True


def findseq(num):
    if num==M:
        print(' '.join(map(str,s)))
    else:
        for i in range(1,N+1):
            s[num]=i
            if promising(num):
                findseq(num+1)

N,M=map(int,input().split())
s=[0]*M
findseq(0)