백트래킹 썸네일형 리스트형 [ 알고리즘 ] 백트래킹 1. 개념 해를 찾다가 해가 아니어서 막히면, 되돌아가면 다시 해를 탐색하는 방법. DFS의 일종. 모든 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 방법. 가지치기. --> 최적화 문제와 결정 문제일 때 2. 방법 DFS 등으로 모든 경우의 수를 탐색할 때, 조건으로 절대 해가 아닌 경우일 때는 탐색을 중단하고 그 이전으로 돌아가, 즉 '백트래킹'해서 다른 경우를 탐색하는 방법으로 주로 구현. 주로 재귀로 구현하다가 조건이 맞지 않으면 종료. 3. 예제 https://www.acmicpc.net/problem/15651 n, m = map(int,input().split()) l = [] def dfs(num): if len(l) == m: for i in l: print(i, end = '.. 더보기 이전 1 다음