송아지 찾기(BFS)

문제

풀이

public class Main {

    static final int max = 20000;
    static int[] visited = new int[max];

    static int[] moving = {-1, 1, 5};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int start = sc.nextInt();
        int end = sc.nextInt();
        System.out.println(solution2(start, end));
    }

    public static int solution(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == end) {
                return visited[current];
            }

            for (int i = 0; i < 3; i++) {
                int next = current + moving[i];

                if (next < 0 || next > max) {
                    continue;
                }

                if (visited[next] == 0 || visited[next] > visited[current] + 1) {
                    visited[next] = visited[current] + 1;
                    queue.add(next);
                }
            }
        }

        return -1;
    }

    public static int solution2(int start, int end){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        int level = 0;
        while(!queue.isEmpty()){

            int length = queue.size();
            for(int i = 0; i<length; i++){
                int index = queue.poll();

                for(int j = 0; j<3; j++){
                    int next = index + moving[j];
                    if(next == end) return ++level;
                    if(next > max || next < 1) continue;
                    if(visited[next] == 0) {
                        visited[next] = 1;
                        queue.add(next);
                    }
                }

            }


            level++;
        }

        return -1;
    }
}

두 버전의 풀이가 있다.
하나는 배열에 이동 횟수를 기록하는 것과,
다른 하나는 아예 level별로 노드를 탐색하는 것이다.

첫 번째는 inflearn답지 버전이고 두 번째는 bfs를 배운대로 내가 풀어본 버전인데
개인적으로 두 번째 풀이가 헷갈리지 않고 조금 더 직관적인 것 같다.