문제

https://www.acmicpc.net/problem/16719

소스

if __name__ =="__main__":
    s = input().strip()
    res = [''] * len(s)

    def func(arr,start):
        if not arr:
            return
        _min = min(arr)
        idx = arr.index(_min)
        res[start+idx] = _min
        print("".join(res))
        func(arr[idx+1:],start+idx+1)
        func(arr[:idx],start)
    func(s,0)

설명

0. 아직 탐색하지 않은 문자열 중에서 사전순으로 먼저 나오는 알파벳 순서로 출력하기
1. 처음에 가장 작은 문자열 탐색
2. 1 에서 찾은 문자 기준으로 앞, 뒤 탐색

• DFS 이용
• 뒷 부분을 탐색하는 소스를 먼저 탐색하도록 한다.