[백준-실버3] 15649번 N과 M(1) (파이썬, 백트래킹, DFS)

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

15649번: N과 M (1)

<복습 체크>

22/03/05
O

 

<내 코드1>

- dfs를 이용해서 백트래킹을 구현했다.

- 스택의 길이가 m개가 되면 출력을한다. (종료조건)

- 조합에서 중복을 허용하지 않으므로 스택에 i가 들어있지 않을때만 추가해준다( 1 1 -> 안됨, 4 4 -> 안됨)

- 일반 dfs와 다른점은 pop을 통해 사용한 원소를 제거해줌으로써 이전의 상태로 돌아갈 수있다.

n,m = map(int, input().split())
stack = []

def dfs():
    if len(stack) == m:
        print(*stack)
        return
    for i in range(1,n+1):
        if i not in stack:
            stack.append(i)
            dfs()
            
            stack.pop()
            
dfs()

 

 

<내 코드2>

- 유튜브 바킹독님 C++코드를 파이썬으로 옮겼다

- 아직 머리가 좀 아프긴함,, 

- isused 배열로 1~N까지 사용된 자연수를 파악하여 중복없는 수열을 만든다.

#입력, m은 수열의 길이
n, m = map(int, input().split())

arr = [0]*m #수열을 나타낼 배열
isused = [False]*(n+1) #자연수 n이 쓰였는지 확인하기 위한 배열

def func(k):
    if k==m: #arr가 가득 차면 -> 수열이 완성 되면
        #출력
        for i in range(m):
            print(arr[i], end = ' ')
        print()
        return
    
    for i in range(1,n+1): #자연수 n만큼 반복
        if isused[i] == False: #아직 사용하지 않았다면
            arr[k] = i #수열의 k번째 완성
            isused[i] = True
            
            func(k+1)#수열의 k+1번째 원소를 위해 재귀호출
            isused[i] = False ##완성했으면 다시 False처리 해줘야 순차적으로 탐색가능
            
#메인 부분
func(0) #함수 호출