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

문제링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

작성코드

 

풀이

 

1. 백트래킹 알고리즘

 

일종의 트리 탐색 알고리즘이다.

현재 상태에서 모든 경로를 따라 뻗어나가다가 가능성이 없다 판단되면 되돌아가서 다시 해를 찾아간다.

알고리즘 구현 방식은 기본 DFS(깊이 우선 탐색) 방식과 동일하게 재귀 호출을 사용하여 노드를 찾는다.

 

※ DFS 방식 구현 (모든 경로를 탐색한다)

 

 

2. 구현

 

1) 숫자 범위 N과 수열 길이 M을 입력받는다, 탐색 값을 저장할 리스트 S를 선언한다.

 

2) 백트래킹 알고리즘은 dfs 깊이 우선탐색 방식에서 가능성이 없는 부분을 가지치기 한다.

수열의 경우 가지치기 되는 부분은 리스트 내 같은 수가 존재하는 경우이다,

( == 리스트 내에 현재 탐색 값이 존재하는 경우를 제거한다)

 

※ 위에서 작성한 dfs에서 가지치기 할 if 문을 추가하면 백트래킹 알고리즘이 완성된다.