백준 1697 java

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

1697번: 숨바꼭질

풀이 방법

 

풀이 코드

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


public class Main{
    static int N;
    static int K;
    static int move[] = new int[100001];
    
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String[] inputs = input.split(" ");
        
        N = Integer.valueOf(inputs[0]);
        K = Integer.valueOf(inputs[1]);
        
        System.out.println(bfs(N));
    }
    
    private static int bfs(int node){
        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.add(node);
        int n = 0;
        int index = node;
        move[index] = 1;
        while (queue.isEmpty() == false){
            n = queue.remove();
            if (n == K)
                return (move[n] - 1);
            if (n - 1 >= 0 && move[n - 1] == 0){
                move[n - 1] = move[n] + 1;
                queue.add(n - 1);
            }
            if (n + 1 <= 100000 && move[n + 1] == 0){
                move[n + 1] = move[n] + 1;
                queue.add(n + 1);
            }
            if (2 * n <= 100000 && move[2 * n] == 0){
                move[2*n] = move[n] + 1;
                queue.add(2 * n);
            }
        }
        return (-1);
    }
}

 

 

최적화시키기

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

public class Main {
    static int N;
    static int K;
    private static final int MAX_POSITION = 100000;
    static int[] time = new int[MAX_POSITION + 1];

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String[] inputs = input.split(" ");

        N = Integer.parseInt(inputs[0]);
        K = Integer.parseInt(inputs[1]);

        System.out.println(bfs(N));
    }

    private static int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int current = queue.remove();
            if (current == K) {
                return time[current];
            }

            moveNode(current - 1, current, queue);
            moveNode(current + 1, current, queue);
            moveNode(2 * current, current, queue);
        }

        return -1;
    }

    private static void moveNode(int next, int current, Queue<Integer> queue) {
        if (next >= 0 && next <= MAX_POSITION && time[next] == 0) {
            time[next] = time[current] + 1;
            queue.add(next);
        }
    }
}