백준 16953 A -> B 풀이/코드 (파이썬) 간단한 dfs문제!

문제 코드만 궁금한 분은 깃허브링크

 

 

문제 설명 :

 

1. [2, 162]와 같이 임의의 두 수가 주어진다.

2. 앞의 수를 2배 하거나 앞의 수의 끝에 1을 붙일 수 있다. 가령 2는 4가 될수도 있고 21이 될 수도 있다.

3. 이 때 2번의 방식을 반복해서 앞의 수를 뒤의 수로 만들 수 있다면 몇 차례나 반복해야하는지를 출력하고, 만일 만들 수 없으면 -1을 출력한다.

 

 

문제 해결 논리:

 

1. 두 수를 받는다.

2. 앞의 수, 0(연산 횟수)을 dfs함수에 넣는다.

3. dfs 함수에서는 다시한번 해당 함수를 2회에 걸쳐 호출하는데(재귀함수), 한번은 입력값*2를, 다른 한번은 입력값+문자열(1)을 각각 dfs에 입력값으로 넣는다.

4. 이 때 dfs함수에 또다른 입력 값으로, 연산 횟수를 넣는다. 가령 이전에 2를 연산 횟수로 받으면 다음번 호출때에는 3을 입력한다.

5. dfs 함수에 종료 조건으로는, 일단 만일 dfs에서 입력받은 값이 우리가 원하는 값이 나오면 입력받은 이전 연산 횟수에 1을 더해서 반환하고,(문제 조건) 만약 입력받은 값이 우리가 원하는 값보다 커지면 그냥 pass한다.

6. 만약 dfs함수가 모두 종료될 때 까지 print되지 않으면 -1을 출력한다.