[백준] 16953번 A → B JAVA (자바) 풀이

문제 16953번 (bfs)

:  정수 A를 B로 바꾸고 필요한 연산의 최솟값을 구해라

 

:  가능한 연산

• X 2
• 수의 가장 오른쪽에 1 추가

 

 [입력]

 :  첫째 줄에 A, B (1 ≤ A < B ≤ 10⁹)

 

 

[출력]

 :  연산의 최솟값에 1을 더한 값을 출력 (만들 수 없는 경우 -1 출력)

 

 [과정]

 

1. int 말고 long

• 사용뒷자리에 1을 추가하게 될 경우 숫자가 너무 커질 수 있다

 

2 - 1. count = 0라면

• while문 초입에서 ++하고 시작

2 - 2. count = 1라면

• while문 끝에서 ++하기

 

3. if문 조건

• 계산한 숫자(p)가 b보다 클 경우, 작을 경우, 같을 경우 딱 세 가지이다
• if(p==b)랑 if(p>b) 만해주고 나머지는 p<b인게 분명하니 if문 사용하지 않았다

 

4. void가 아닌 int 사용

• void를 사용하려면 return이 아닌 System.out.println으로 바로 출력해야 한다
• return을 사용하기 위해서 int로 변경
• long과 헷갈리지 말아야 하는게 입력은 long타입이지만 연산의 횟수는 int count로 받기 때문에 자료형은 int로 한다 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static long a,b;
    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());

    }
    static int bfs(){
        Queue<Long> q = new LinkedList<>();
        q.add(a);
        int count =0;
        
        while(!q.isEmpty()){
            count++;
            int size = q.size();
            for(int i=0;i<size;i++){
                long p = q.poll();
                if(p==b)
                    return count;
                if(p>b)
                    continue;
                q.add(p*2);
                q.add(p*10+1);
            }
        }
        return -1;
    }
}

 

 [해설]
     

 :  static long a,b;
  

 :  a = Long.parseLong(st.nextToken());  입력1
    b = Long.parseLong(st.nextToken());  입력2
        
 :  System.out.println(bfs());  바로 bfs 출력

 :  static int bfs(){  bfs 시작
        Queue<Long> q = new LinkedList<>();  큐 선언
        q.add(a);  큐에 입력1 넣고 시작
        int count =0;  카운트 초기화
        
        while(!q.isEmpty()){
            count++;  연산횟수 ++ 하고 시작
            int size = q.size();  
            for(int i=0;i<size;i++){  큐 사이즈만큼 반복
                long p = q.poll();  다시 연산하기 위해 큐에서 빼기
                if(p==b)  b랑 같아지면 바로 카운트 출력
                    return count;
                if(p>b)  b보다 커지면 연산 의미가 없기 때문에 반복문 종료
                    continue;
                q.add(p*2);  b보다 아직 작다면 계속해서 연산
                q.add(p*10+1);  b보다 아직 작다면 계속해서 연산
            }
        }
        return -1;  답이 없을 경우 -1 출력
   }

   

 

      

이제 풀어보러 갈께요 :)

 

 

 

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *