백트래킹(Backtracking)

 

 

백트레킹이란? 

특정 제약 만족 문제에 대한 해결책을 찾기 위해 사용하는 알고리즘으로,

해결책에 대한 후보를 점진적으로 접근하고, 접근하던 후보가 유효한 해결책으로 완성될 수 없다고 판단되는 즉시 바로 전에 후보로 후퇴하여 다른 후보로 접근한다. 

---

 

이미지로 보면 이러하다 .

 

다 끝날 때 모든 경우의 수 에 접근한 상태다.

사실 미로찾기와 같다. 미로찾기하면 무슨 알고리즘이 생각나는가? 바로 DFS다. 

백트레킹은 완전 탐색의 한 종류인데 DFS를 활용하여 사용할 수 있다.

---

이번에는 그래프를 잠깐 잊고 아래 문제를 풀어보자

 

1759번: 암호 만들기

 

 

이전에 말했듯이 DFS를 재귀 혹은 Stack 으로 할 수 있는데

재귀로 구현할 시에 현재의 정보와 BASE CASE가 필요하다고 했다. 이점을 참고하고 보자 

 

1. 일단 처음 CNT(명시적 매개변수) 즉 ,만든 단어의 길이가 주어진 C의 개수와 같아질 떄 해당 메서드에 자음와 모음의 개수를 체크하고 조건을 만족할 시에 출력한다. BASE CASE 

 

2.아직 BASE CASE에 도달하지 못해 진행할 RECURSIVE CASE는 idx 즉, 현재 인덱스(명시적 매개변수) 부터 단어의 개수 만큼  words의 인덱스를 뽑아  answer에 추가해준다. 

 

이게 다다.

 

import sys


def back_tracking(cnt, idx):

    if cnt == l:
        mo, ja = 0, 0

        for i in range(l):
            if answer[i] in consonant:
                mo += 1
            else:
                ja += 1

        if vo >= 1 and co >= 2:
            print("".join(answer))

        return

    for i in range(idx, c):
        answer.append(words[i])
        back_tracking(cnt + 1, i + 1)
        answer.pop()


l, c = map(int, sys.stdin.readline().split())
words = sorted(list(map(str, sys.stdin.readline().split())))
consonant = ['a', 'e', 'i', 'o', 'u']
answer = []
back_tracking(0, 0)

---

모든 경우를 탐색했다.

실패하더라도 탐색했다. 

깊이있게 끝까지 가서 유효한가를 확인했다.

 

그러나 그래프를 사용했는가? 

그렇지 않다.