[ 백준] 15650번 : N과 M (2) (파이썬)

문제 )

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

15650번: N과 M (2)

 

[ 풀이 ]

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

 

- Backtracking Algorithm 이란? 

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

 

- Node가 Promising한지 점검하는 법 

✔ 수열에 중복되는 값이 없어야한다
✔ 수열이 오름차순이어야한다

 

수열에 중복되는 값을 없애고 원소들이 오름차순인지 유망성을 검사하는 함수를 따로 만들었다 

 

< promising Function >

수열 list s의 원소들이 중복값이 없고 오름차순이기 위해서 s의 원소들을 index 0 ~ M까지 유망성을 검사할때
그 전 index 의 원소보다는 항상 값이 커야한다. 

예를 들어 , s의 s[0]=2라면 s[1]의 값은 무조건 2보다는 커야만 한다. 
그러므로 Promising Function은 s[n-1]<s[n]이면 True를 , s[n-1]>=s[n]이면 False를 반환하는 함수이다.

 

 

< findsequence 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(n):
    if n!=0:
        if s[n-1]>=s[n]:
            return False
    return True


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

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