[ 백준 ] 15649번 : N과 M (1) (파이썬)

문제 )

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

15649번: N과 M (1)

 

[ 풀이 ]

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

 

- Backtracking Algorithm 이란? 

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

 

- Node가 Promising한지 점검하는 법 

✔ 수열에 중복되는 값이 없어야한다

 

수열에 중복되는 값을 없애려고 유망성을 검사하는 함수를 따로 만들었다 

< promising Function >

list s의 원소의 count를 확인해보고 1이상이면 중복된 값이 있다고 판단하여 False를 반환한다.

첫번째로 푼 코드이다. 

- python code 1

def promising(n):
    if n==0:
        return True
    if s.count(s[n])!=1:
        return False
    return True

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

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

 

그러나 다 풀고 나서 다른분들이 푼 답안을 확인해보니 더 쉽게 푸는 방법이 있었다,,

그래서 다른 사람들의 방법으로 한번 더 풀어보았다. 
1~N까지의 숫자중 사용하고 있는 숫자를 True로 만들어주는 list (check)를 만들어서 문제를 풀었다. 

 

< findseq Function의 Algorithm >

✔ 1~N까지의 숫자를 사용하고 있는지 알려주는 list →  check (사용 안 할 경우 → False )
✔ 초기화 된 수열 → s
✔ 수열의 index에 접근하는 변수 → n (0부터 M까지)

If list s에 M자리까지 숫자가 중복없이 채워진 경우 (수열이 완성된 경우)
           1. 수열 s를 출력
Else
           1. 값을 하나씩 늘려가는 index → i (1~N+1)
                     If i값이 중복되지 않는 경우
                                 Ⅰ.  i값이 사용되고 있다고 check해주고
                                        →  s[n]에 i값을 넣어준다
                                 Ⅱ.  n+1번째 index에 대해서 findseq function 실행하고
                                        →  끝나면 check[i]를 False로 바꿔준다. (사용 끝이기 때문)

 

- python code 2

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

N,M=map(int,input().split())
check = [False for i in range(N + 1)]
s=[0]*M
findseq(0)