백트래킹 - 백준 10597 (22.6.14)

사용자가 특정 차트를 고르면, 전 종목의 과거(10년) 차트들을 모두 탐색하여 가장 유사한 차트 10개를 골라 사용자에게 보여줍니다.

 

웹프로젝트 링크

비슷한 차트 검색기

 

 

 

백트래킹이란

 

백트래킹(backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.

 

즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기하는 것을 백트래킹이라고 생각하면 된다.

 

 

깊이 우선 탐색(DFS) 과 백트래킹

 

DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.

 

따라서, N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 어렵다.

예시 : 백준 10597번 문제

50개의 수를 나타내는 순열의 경우의 수는 50!로 완전 탐색으로는 풀 수 없다. 왼쪽부터 숫자를 하나하나 살펴보며 가능한 순열을 만들어 출력해야 한다.

 

예를 들어 1을 만나면 1을 취할 수도 있고, 1 다음에 나오는 숫자와 합쳐서 두 자릿수를 취할 수도 있다. 만약 이 전에 1을 이미 고른 적이 있다면 두 자리 수를 취할 수밖에 없다. 그런데 이 1이 마지막 숫자라서 다음 숫자가 없다면 순열 만들기에 실패한 것이므로 돌아가서 다른 방법을 찾아야 한다.

 

이런 전략으로 백트래킹으로 풀 수 있다.

inpu = input()
N = (len(inpu) - 9) // 2 + 9 if len(inpu) > 9 else len(inpu)
check = [False] * (N + 1)
find_ans = False

def bt(i, arr):
    global find_ans
    if i >= len(inpu): # 숫자를 다 썼으면 정답
        find_ans = True
        print(*arr)
        return

    n = int(inpu[i])
    if n <= N and not check[n]: # 일단 안쓴숫자면 끼워맞춰보고
        check[n] = True
        narr = arr[:]
        narr.append(n)
        bt(i + 1, narr) # DFS 돌려봐서
        if find_ans: 
            return    
        check[n] = False # 이숫자로 답안나오면 취소하고

    if i + 1 < len(inpu):
        n = int(inpu[i:i+2]) # 두자리 수로 해보기.  결국엔 두가지 경우중 하나다
        if n <= N and not check[n]:
            check[n] = True
            narr = arr[:]
            narr.append(n)
            bt(i + 2, narr)
            if find_ans:
                return
            check[n] = False

bt(0, [])