문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/154538

정답 코드

import java.util.*;

class Solution {

    public int solution(int x, int y, int n) {

        return bfs(x, y, n);
    }

    public static int bfs(int x, int y, int n) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[y + 1];
        queue.add(new int[]{x, 0});
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curX = current[0];
            int curCount = current[1];

            if (curX == y) return curCount;

            if (curX < y) {
                for (int i = 0; i < 3; i++) {
                    int[] dx = {curX + n, curX * 2, curX * 3};
                    int nx = dx[i];
                    if (nx > y) break;

                    if (!visited[nx]) {
                        queue.add(new int[]{nx, curCount + 1});
                        visited[nx] = true;
                    }
                }
            }

        }
        return -1;
    }


    public static void main(String[] args) {
        int x = 10;
        int y = 40;
        int n = 5;
        Solution sol = new Solution();
        System.out.println(sol.solution(x, y, 5));
    }
}

데이터 입력값이 매우 커 시간초과에 잘 신경써야 하는 문제이다. boolean의 vistied 배열을 만들고 각 인덱스에 해당하는 값을 방문했으면 해당 인덱스를 true로 만들어서 방문처리하면 되는 전형적인 BFS 문제이다.