알고리즘 백트래킹에 대해 알아보자

서론

 

흠.. 특별히 쓸 글이 없어서 오늘은 백트래킹에 대해 알아보려한다. 백트래킹을 알면 백준 골드 문제도 많이 풀 수 있으니, 같이 오늘 알아보도록 하자.

 

본 내용과는 관련없지만, 심심하니 올린다.

백트래킹이 뭘까?

 

그대로 번역하면 뒤를 쫓다 정도의 해석이 가능하겠다. 하지만 실제 알고리즘은 그런 내용은 아니다. 백트래킹은 완전탐색의 연장선인데, 완전탐색을 하되, 굳이 탐색할 필요 없는 구간은 배제해버리고 완전탐색을 돌리는 것이다. 그렇기 때문에 당연히 재귀함수 혹은 for문을 사용하여 구현을 한다. DFS 개념에서도 방문하는 정점이 비효율적일 경우 배제하면서 순회하는 것 또한 백트래킹이라고 할 수 있다.

 

원래는 N-Queen 문제가 백트래킹의 유명한 문제인데, 아직 풀지 않아서 다른 문제를 올리도록 하겠다.

 

이제 백준 문제를 통해 백트래킹 문제를 풀어보고 코드를 올리도록 하겠다.

 

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

 

 

 

 

 

 

 

 

 

필자의 코드

import sys
l, c = map(int, sys.stdin.readline().split())
alpha = sorted(list(sys.stdin.readline().split()))

list1 = []
idx = 0
def password(idx):
    count = 0
    if len(list1) == l and ('a' in list1 or 'e' in list1 or 'o' in list1 or 'u' in list1 or 'i' in list1):
        for i in range(l):
            if list1[i] in ['a','e','i','o','u']:
                count += 1
        if l-count > 1:
            print(''.join(list1))
            return
    for i in range(idx,c):
        if alpha[i] in list1:
            continue
        if len(list1) > 1 and ord(alpha[i]) < ord(list1[-1]):
            continue
        list1.append(alpha[i])
        idx += 1
        password(idx)
        list1.pop()

password(idx)