백준(baekjoon) 15649번: N과 M (1) (실버 3, 파이썬 PYTHON) - 백트래킹

문제

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

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

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

15649번: N과 M (1)

 

 

import sys

N,M=map(int,sys.stdin.readline().split())
list=[]

def dfs(num):
  global N,M,list
  if(num==M):  
    print(*list) 
    return 
  for x in range(1,N+1): 
    if x not in list: 
      list.append(x)  
      dfs(num+1)  
      list.remove(x) 

dfs(0)

 

※ 백트래킹

 

 

● 먼저 list 배열과 함수 dfs() 를 선언해준다.

 

● 함수 dfs()의 매개변수는 각 단계에서 list에 들어있는 원소의 개수를 의미한다. 맨 처음 시작할 때에는 list가 비어있으므로 dfs(0) 부터 시작한다.

 

이제 함수 dfs() 안을 살펴보자.

 

● 먼저 매개변수는 list에 들어있는 원소의 개수를 의미한다 했으므로 M의 값과 같은 값의 매개변수가 들어오면 현재 list에 있는 요소들을 출력한 후 return 해준다.

 

● 매개변수가 M의 값보다 작으면 1부터 N까지의 수를 차례대로 돌며 만약 list에 이 값이 없을 시 list에 append 해주고, list 요소의 개수가 1 늘어났으므로 현재 매개변수 값에 1을 더한 값을 함수 dfs()의 인수로 넣어 호출한다.

 

● 각 dfs() 함수가 return 되면 각 단계에서 append 해주었던 숫자들을 list에서 제거해준다.

 

 

결과

 

 

♣ 참고: 백트래킹

 https://fomaios.tistory.com/entry/Algorithm-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking%EC%9D%B4%EB%9E%80

[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함)