BOJ_16953 A ->B [Java] (S1)

문제 설명

풀이

보자마자, DP, 와 BFS가 바로 생각났다. 그래서 바로 BFS로 풀었는데, 처음에는 visit을 해쉬맵(map)이 아닌 배열로 했다가 메모리 초과가 계속 떠서 더 찾아보니 HashMap으로 하면 더 빨라서 바로 바꾸었다.

 

그래도 계속해서 오답이 나오길래, Int에 문제가 있는 것 같아서 바로 Long으로 바꿔보니 통과했다.

역시 Input값의 범위도 항상 잘 봐야겠다.

 

코드

첫번째 코드 - 틀림

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[M+1];
        count = 0;

        count = bfs();
        System.out.println(count);
    }

    private static int bfs() {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {N,0});
        visit[N] = 0;

        while (!que.isEmpty()) {
            int[] out = que.poll();

            if (out[0] == M) return out[1] + 2;
            if ( out[0] * 2 <= M && visit[out[0]*2] == 0 ){
                visit[out[0] * 2] = out[1]+1;
                que.add(new int[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && visit[out[0] * 10 + 1] == 0 ){
                visit[out[0] * 10 + 1] = out[1]+1;
                que.add(new int[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}

완성된 코드 - 정답

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static long count;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = bfs();
        if(count == -1)
            System.out.println(count);
        else
            System.out.println(count+1);
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && !map.containsKey(out[0] * 10 + 1) ){
                map.put(out[0] * 10 + 1, out[1]+1);
                que.add(new long[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}