🥚문제링크

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

• 그래프 이론
• 그리디 알고리즘
• 그래프 탐색
• 너비 우선 탐색

---

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

A, B = map(int, input().split())


def bfs(num):
    q = deque([])
    visited = set()
    q.append((num, 0))
    visited.add(num)

    while q:
        num, cnt = q.popleft()

        if num == B:
            return cnt + 1

        x = num*2
        y = num*10 + 1

        if x <= B and x not in visited:
            visited.add(x)
            q.append((x, cnt+1))

        if y <= B and y not in visited:
            visited.add(y)
            q.append((y, cnt+1))

    return -1


print(bfs(A))

---

🧂아이디어

BFS

• A에서 시작하는 BFS를 진행한다.
• 큐에는 (num(숫자), cnt(연산횟수)) 를 담는다.
• num이 B가 되면 cnt + 1을 리턴한다.
• num * 2, num * 10 + 1 숫자를 방문한 적 없고, B 이하라면 큐에 (num * 2, cnt + 1), (num * 10 + 1, cnt + 1)를 담는다.
• 큐가 비어서 더이상 탐색을 할 수 없다면 -1을 리턴한다.