[코테] 백준 16953 A->B | BFS Java

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

 

테스트 케이스는 모두 잘 나오고, 게시판 반례들도 잘 나오는데 4%에서 틀렸다고 나왔다.

 

틀린 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/16953
public class baekjoon_16953 {
    private static int 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 = Integer.parseInt(st.nextToken()); // 기본 값
        B = Integer.parseInt(st.nextToken()); // 변경할 값

        bfs();
    }

    static void bfs(){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(A, 1));

        while(!que.isEmpty()){
            Point p = que.poll();
            for(int i =0; i<2; i++){
                int next = p.x;
                if(i==0) {
                    next = next * 2;
                } else {
                    next = next * 10 + 1;
                }

                if(next == B) {
                    System.out.println(p.y + 1);
                    return;
                }

                if(next < B){
                    que.add(new Point(next, p.y+1));
                } else if (que.isEmpty()) {
                    System.out.println(-1);
                    return;
                }

            }
        }
    }

}

 

next 뒤에 1을 붙이는 걸 원래 next = Integer.parseInt(next + "1");로 했었는데 java.lang.NumberFormatException 오류가 나길래 수정했다.

 

틀린 부분

아무리 봐도 틀린 게 없었는데 게시판에서 이 글을 보았다.

https://www.acmicpc.net/board/view/158122

혹시나 해서 int -> long으로 변경. 성공했다.

입력값에는 문제가 없는데, 내가 next뒤에 1을 붙이면서 오버플로우가 발생한 것이었다!

 

최종 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/16953
public class baekjoon_16953 {
    private 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 = Integer.parseInt(st.nextToken()); // 기본 값
        B = Integer.parseInt(st.nextToken()); // 변경할 값

        bfs();
    }

    static void bfs(){
        Queue<CustomPoint> que = new LinkedList<>();
        que.add(new CustomPoint(A, 1));

        while(!que.isEmpty()){
            CustomPoint p = que.poll();
            for(int i =0; i<2; i++){
                long next = p.x;
                if(i==0) {
                    next = next * 2;
                } else {
                    next = next * 10 + 1;
                }

                if(next == B) {
                    System.out.println(p.y + 1);
                    return;
                }

                if(next < B){
                    que.add(new CustomPoint(next, p.y+1));
                } else if (que.isEmpty()) {
                    System.out.println(-1);
                    return;
                }

            }
        }
    }

    public static class CustomPoint {
        long x;
        long y;
        public CustomPoint(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }


}

혼자 힘으로 다 해결해서 뿌듯하다~ 어제 풀었던 거랑 비슷해서 금방 푼 것 같다