백트래킹

 

모든 경우의 수를 확인해야 할때. 

하지만, FOR로는 확인이 불가능 할 때 사용한다

EX) FOR문의 수를 몇번 써야할지가 , M,N과 같은 변수로 들어올 때(변수 일때) 사용한다.

 

백 트래킹의 구조를 생각해보자. 

1. 재귀 함수로 확인 

2. 재귀를 벗어나는 조건 IF NUM == N : BREAK 

(def rec (num): 일때, if num == N : break와 같은 형태로 주로 사용한다)

3.  아닐때 FOR(~~ -> 재귀)

 

핵심! 이 check 과정에서, 방문 여부를 확인해야한다.

 

시간 복잡도 확인 방법

중복이 가능할때는 N(선택할 수 있는 수) ^ M (깊이)

중복이 불가능할때는 N! (알고리즘때 들었던 내용을 기억하자) <2억이어야 한다. 

 

 

방문 여부를 확인하는 자료구조, 입력을 받는 자료구조가 필요하다.

++ 순열과 같은 경우에서, 그 경우의 수들을 저장하는 순열 resultlist = []등이 필요할 수 있다.

 

EX) 백준 15649

import sys

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

visited = [False] * (N+1)
resultlist = []

def backtracking(num):

    if num == M :
        print(' '.join(map(str,resultlist)))
        return
    
    for i in range(1,N+1):
        if visited[i] == False and i not in resultlist:
            visited[i] == True
            resultlist.append(i)
            backtracking(num+1)
            visited[i] == False
            resultlist.pop()


backtracking(0)

 

 

1. N개중 M개를 구해 모으는 문제

2. 중복이 불가

3. 자료구조 -> 방문하였는가를 확인할 VISITED, 정답 객체를 모아둘(! 중요하다. 이걸 RETURN하지 않더라도 모아둔 후 확인한다) RESULTLIST

4. resultlist에 하나씩 추가

5. backtracking 으로 depth를 1개씩 증가

6. depth가 M (resultlist에 들어온 갯수가 M개 시 RETURN)

7. 다시 중요! 한번 DETPH의 끝까지 가고 난 후는, VISITED도 RESULTLIST도 POP해주어야 한다. 

 

TIP : N의 갯수가 작을때, 백트래킹을 고려해 보자(주로 8~10 미만)

 

 

백준 1182 : 답이 다르게 나왔다. 

그 문제는, 부분 수열의 값을 고를때 중복을 제거하여야 했기 때문이다. 

 

그러므로 마치 0-1 knapsack처럼, 다음걸 고른다 안고른다..의 선택지만 주었다. 

 

 

다음 원소를 선택 or 안선택으로, 복잡도 또한 2^N으로 변경되었다. 

이러한 방식의 백트래킹이 있음을 주의 해야겠다. 

 

** 이전엔, 일단 다음 원소를 넘길때 total+alist[]하는 형태로 넘겼는데,

그것을 일단 더하고, 다음걸 빼는 방식으로 구현하였다. 

 

 

 

이런 식으로.. 이때는 근데 몇개가 더나왔다. 

 

 

출처 : https://im-gonna.tistory.com/78

 

그 이유는. 공집합이 계속 걸리기 때문! 
그러므로 일단 다음 원소를 더하고 -> 검증 후 -> 선택 안해주기, 해주기로 변경하였다.