[백준/JAVA] 16953번: A → B

🔺 문제

16953번: A → B

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static long A, B;
    static int  cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
        
        System.out.println(BFS(A));
    }
    
    static long BFS(long n) {
        Queue<Long> queue = new LinkedList<>();
        queue.add(n);
 
        while(!queue.isEmpty()) {
            int size = queue.size();    // 현재 큐 크기 미리 저장해둬야 함!!!
            
            for(int i = 0 ; i < size ; i++) {
                long now = queue.poll();
                
                if(now == B) {
                    return cnt + 1;
                }
                
                if(now * 2 <= B)       queue.add(now * 2);
                if(now * 10 + 1 <= B)  queue.add(now * 10 + 1); 
            }
            cnt++;
        }
        return -1;
    }
}

✅ 해결 아이디어
✔ DFS / BFS

 

💥 유의사항

• 23번째 줄 ⇨ 현재 큐 크기 변수 미리 저장해두고 사용해야 함!!! 이래야 해당 크기만큼 반복해 한 단계씩 진행하면서 같은 단계의 노드들 올바르게 처리 가능.
(안 그러면 한 단계 노드들을 모두 처리하기 전에 큐의 크기가 계속 변해, 예상치 못한 동작이 발생한다 함)

 

 

---

🔺 다른 풀이들

- [그리디]  B에서부터 줄여가는 접근 방법으로 거꾸로 푸셨다.

[백준 16953] A → B with JAVA

[BOJ] 백준 16953번 : A -> B (JAVA)

 

- [DFS]

[백준] 16953번 A->B (자바 풀이)

 

---

💬 느낀 점

인접 행렬 / 리스트도, 방문 배열도 필요 없고

생각보다 정답 코드가 간단해서 조금 놀랐다

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 16953번( 자바 )