[백준 코딩테스트] 25418번 정수 a를 k로 만들기

풀이

이 코드는 동적 계획법을 사용하거나 BFS를 사용해서 최소 연산 횟수를 구해야한다.
BFS의 경우 이미 답을 발견했는데에도 끝까지 탐색하기 때문에 메모리로 인해 테스트에 통과하지 못한다.

처음에는 어떤 방식으로 접근하는지 감이 잡히지 않아 무작정 무한루프를 통해 접근하려다 보니 문제를 해결하는 데에 1시간이 넘게 걸린 것 같다.

Queue<int[]>를 사용해 큐에 연산1과 연산2를 적용한 값을 넣고 카운트를 한다.
이때 연산2가 항상 연산1의 값보다 앞서기 때문에 연산2를 적용한 값만 방문 여부를 체크한다. 방문하지 않은 값이라면 연산1을 적용한다.

내 코드

import java.util.*;

public class Main {
    static int k, a;

    static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[k+1];

        visited[a] = true;
        q.offer(new int[]{a, 0});

        while(!q.isEmpty()){
            int[] curr = q.poll();
            if(curr[0] == k){
                System.out.println(curr[1]);
                return;
            }
            if(curr[0]*2 <= k){
                visited[curr[0]*2] = true;
                q.offer(new int[]{curr[0]*2, curr[1]+1});
            }
            if(!visited[curr[0]+1]){
                q.offer(new int[]{curr[0]+1, curr[1]+1});
            }
        }


    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        a = in.nextInt();
        k = in.nextInt();

        bfs();
    }

}