Q. 개념

---

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아
지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음
과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수
있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성
하세요.
▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000
까지이다.
▣ 출력설명
점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.
▣ 입력예제 1
5 14
▣ 출력예제 1
3
▣ 입력예제 2
8 3
▣ 출력예제 2
5

전략

• BFS(레벨탐색)는 (이진트리를 포함한 상태트리에서) 주로 최단거리 알고리즘에 사용된다.

  최단거리 알고리즘 키워드
  "최소 횟수인 거리~"

• 5가 루트노드이고, 한 루트노드에서 다음 레벨(=한번의 점프)로 가기위한 경우의 수는 세가지(1, -1, 5)이다. 14를 찾을때 까지 계속 다음레벨로 뻗는다.
• 점프 횟수 = 레벨
• 단, 시간복잡도를 줄이기 위해 이미 나온 숫자(=이미 방문한 노드)는 큐에 넣지 않는다.
• 트리구조

  

정답

import java.util.*;
class Main {
    int answer=0;
    int[] dis={1, -1, 5};
    int[] ch;
    Queue<Integer> Q = new LinkedList<>();
    public int BFS(int s, int e){
        // 좌표 최대 범위만큼 배열의 크기를 잡는다. 0번 인덱스는 사용하지 않음
        ch=new int[10001];
        //출발지점 s에 대해 방문함을 체크
        ch[s]=1;
        //방문
        Q.offer(s);
        int L=0;
        while(!Q.isEmpty()){
            // 해당 레벨의 모든 노드들의 개수
            int len=Q.size();
            for(int i=0; i<len; i++){
                int x = Q.poll();
                for(int j=0; j<3; j++){
                    int nx=x+dis[j];
                    if(nx==e){
                        // 답은 반드시 존재하므로(문제조건) 무조건 여기서 return 된다.
                        // L은 x의 레벨값이므로 nx의 레벨값은 L+1
                        return L+1;
                    }
                    // nx>=1 && nx<=10000 : 좌표 범위 제한
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        ch[nx]=1;
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        // 무조건 중간에서 return되지만 반환형이 int이므로 문법에러 방지를 위해 임의의 수 리턴
        return 0;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int s=kb.nextInt();
        int e=kb.nextInt();
        System.out.println(T.BFS(s, e));
    }
}