재귀 DFS 문제: 단어 최소 사용 개수 구하기

 

 

그동안 풀어왔던 재귀문제는 level의 수가 정해져있었다.

하지만 이 문제는 level의 수가 정해져있지 않아서 처음에 생각을 잘 해야한다.

종료조건을 생각해보면

1) 재귀를 돌면서 만들어진 글자가 내 목표글자보다 길다면 return

(목표글자보다 길어졌다면 계속  뒤에 글자를 추가해봤자 목표글자가 안됨)

2) 만들어진 글자가 목표글자랑 똑같다면, 몇개 글자 붙힌건지 출력

 

 

 

 

두번째 종료조건에 맞는 조건을 먼저 써줬다.

cnt(내가 몇개 글자 이어붙힌건지 표현하는 변수)를 매개변수로 설정하였다.

arr = ['BTS', 'SBS', 'BS', 'CBS', 'SES']
path = ['']*30
word = input()

def recur(level, cnt):

   if ''.join(path)==word:
       print(cnt)
       return

첫번째 종료조건

   if len(''.join(path))>len(word):
       return

글자를 하나씩 이어붙히면서 다음 글자를 찾는다.

   for i in range(len(arr)):
       path[level] = arr[i]
       recur(level+1, cnt+1)

recur(0,0)

이렇게 쓰면, 재귀에서 빠져나올때 문제가 생긴다.

새로운 단어 만들면서 path 배열을 계속 초기화해야하는데

자꾸 내가 지금 있는 level의 값만 대체하게 된다.

 

 

그래서 재귀를 빠져나올 때, 방금 넣은 글자를 다시 빼줘야 한다.

   for i in range(len(arr)):
       path[level] = arr[i]
       recur(level+1, cnt+1)
       path[level]=''

recur(0,0)

수정한 코드이다.

 

 

 

전체 풀이는 이러하다.

arr = ['BTS', 'SBS', 'BS', 'CBS', 'SES']
path = ['']*30
word = input()

def recur(level, cnt):

   if ''.join(path)==word:
       print(cnt)
       return

   if len(''.join(path))>len(word):
       return

   for i in range(len(arr)):
       path[level] = arr[i]
       recur(level+1, cnt+1)
       path[level]=''

recur(0,0)