[백준] 16953 A → B (실버2)

문제요약

나의 코드 및 설명 - DFS 활용

• DFS를 활용하여 문제를 해결하였다.

def dfs(depth, temp):
    global a,b
    if temp >= b:
        if temp == b:
            result.append(depth)
        return
    dfs(depth+1, temp*2)
    dfs(depth+1, int("".join(map(str, (list(map(int, str(temp)))+[1])))))

a, b = map(int, input().split())

result = []

dfs(0,a)

if result:
    print(min(result)+1)
else:
    print(-1)

다른 코드 및 설명 - BFS 활용

• BFS를 활용하여 문제를 해결하였다.
• 큐에 다음 숫자와 연산의 개수를 추가한다.

from collections import deque

def bfs(a,b):
    queue = deque()
    queue.append((a,1))
    
    while queue:
        next_num, depth = queue.popleft()
        if next_num > b:
            continue
        if next_num == b:
            result.append(depth)

        queue.append((int(str(next_num)+"1"),depth+1))
        queue.append((next_num*2, depth+1))

a,b = map(int, input().split())

result = []
bfs(a,b)

if result:
    print(min(result))
else:
    print(-1)

피드백

비슷한 유형의 문제를 여러 번 풀어봤었고, DFS를 활용하여 문제를 간단하게 해결하였다.