[완전탐색] 백준 1759 파이썬 풀이(백트래킹을 곁들인)

 

백준 1759.

의식의 흐름 알고리즘

우선 정렬이 되어야하고

그게 주어진 L길이 형태로 어떤 문자열이 있나 출력해봐라~

최소 한개 모음, 두개 자음 필수.

문제자체는 간단하다. 근데 조건들이 좀 있고 출력을 하라니까 오히려 더 헷갈림.. 대충 재귀같은걸 쓸 것 같긴한데 어떻게 구현해야할지.. 훔..

 

찾아보니 백트래킹을 이용하여 문제를 풀어야 하는 것이다. 백트래킹을 다시 알아보자.

 

 

최종 알고리즘

우선 백트래킹을 알아보고 왔다면 재귀로 푸는 부분은 이해했을 것이다.

def back_tracking(): 이라는 함수가 있다고 가정하고

이 때 필요한 것은 '몇 번째 인덱스를 구하는데 사용되고 있는 함수이냐'

그리고 'return 시킬 조건'은 무엇이냐 가 가장 큰 전제 조건이다.

def bf15():
    L, C = map(int, input().split())
    
    arr = list(map(str, input().split()))    
    arr.sort()
    res = []
    vowel = ['a','e','i','o','u']
    
    def verify(idx):
        nonlocal res
        if len(res) == L:
            v, c = 0, 0
            for i in range(L):
                #자,모음 개수 확인
                if res[i] in vowel :
                    v += 1
                else :
                    c += 1
            #조건 만족 시 출력 그리고 재귀 종료
            if v>=1 and c >=2 :
                print("".join(res))
            return
    
        for i in range(idx, C):
            res.append(arr[i])
            verify(i+1)
            res.pop()
    
    verify(0)