송아지 찾기(BFS)

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

최소 - bfs를 이용해서 푸는 문제일 확률이 높다

bfs - 최단 거리를 구하는 알고리즘

 

앞, 뒤, 앞으로 많이 3가지 경우를 bfs로 풀어가며 체크 배열을 사용해서 그 값을 이미 방문한 적이 있는지 확인한다

while문의 내부에서는 처음 노드의 값을 꺼낸 후 큐의 길이만큼 for문을 돌면서 큐에 맨 앞 요소를 꺼내고 

그거에 이동 가능한 좌표를 더한게 찾는 좌표와 같은지 for문으로 돌면서

그게 방문하지 않고 이동 가능한 좌표면해당 인덱스의 체크 배열을 방문한 걸로 바꾸고 좌표값을 큐에 넣어준다

 

방문 여부를 체크하는 배열을 만들고 큐가 비어있지 않는 동안 큐의 길이만큼 돌면서 임시값에 자식 노드 값을 더한다!

 

import java.util.*;

public class Main{
    public int bfs(int s, int e){
        int ans = 0;
        //현수가 앞으로 갈수 있는 횟수
        int[] dis = {-1,1,5};
        //방문 여부 체크 배열, 좌표가 1~10000까지여서 ch배열의 크기를 10001로 설정
        int[] ch = new int[10001];;
        Queue<Integer> q = new LinkedList<>();

        //시작지점 좌표 체크해주기
        ch[s] = 1;
        //큐에 시작 지점 좌표값 넣어주기
        q.offer(s);
        int L = 0;
        while(!q.isEmpty()){
            int len = q.size();
            for(int i =0; i < len; i++){
                int tmp = q.poll();

                //값이 같으면 해당 레벨을 리턴, 이건 큐에 넣지만 밑에 자식 노드의 값을 구했을때 리턴하면 큐에 넣는 단계를 거치지 않아도 된다
                if (tmp == e) ans = L;
                //이동
                for(int j = 0; j < dis.length; j++){
                    //현재 노드의 자식 노드의 값을 더해서 변수로 들고있기
                    int nx = tmp + dis[j];
                    //자식 노드의 값이 좌표 벗어나지 않으면서 방문한 적이 없으면
                    if(nx >= 1 && nx <= 10000 && ch[nx] == 0){
                        ch[nx] = 1;
                        //큐에 자식노드를 더한 값 값 넣어주기
                        q.offer(nx);
                    }
                }
            }
            L++;
        }
        return ans;
    }


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