BFS 백트랙킹_백준(16953)

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

🚨오늘의 학습🚨

BFS 백트랙킹 ➡️ 최소비용 구하기

🔅 모든 경우를 다 보는 게 아니라❌, 도달 가능성🙆🏻‍♂️ 있는 것만 큐에 넣음

🎯 접근 POINT

질문	답변
DFS인가요, BFS인가요?	✔️ BFS입니다. 최단 거리(연산 수 최소)를 요구하니까요.
왜❓ DFS가 아닌가요❓❓	DFS는 먼저 도착한 경로가 최단 보장되지 않음. BFS는 도착 즉시 최단 보장됨
백트래킹은 어디서 나오나요?	조건을 만족하지 않으면 탐색 중단 → 분기 제거가 백트래킹처럼 동작

---

package com.example.algorithm.graph.BFS;

import java.io.*;
import java.util.*;

public class BJN_16953 {

    static class Node {
        long num;
        int step;

        public Node(long num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        Set<Long> visited = new HashSet<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(a, 1));

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            if (cur.num == b) {
                System.out.println(cur.step);
                return;
            }

            if (cur.num > b || !visited.add(cur.num)) {
                continue;
            }

            queue.offer(new Node(cur.num * 2, cur.step + 1));
            queue.offer(new Node(cur.num * 10 + 1, cur.step + 1));
        }

        System.out.println(-1);
    }
}