★송아지 찾기1(BFS)

 

현수의 위치에서 3갈래로 (앞으로 1,뒤로 1, 앞으로 5) 레벨 탐색하면된다.

이동한 위치에 대해서 방문처리 해주는 배열이 필요하다. - 길이는 10001

여기서 방문처리의 이유는 효율성 때문이다.

5번 위치에서 뻗어나가다가 5번 위치가 되었을 때 그 5번 위치에 또 탐색하는 것은 비효율적이다.

 

import java.util.*;

public class Main {
    int answer = 0;
    //3가지 점프 종류
    int[] dis = {1, -1, 5}; 
    //방문했던 위치인지 확인하는 배열
    int[] ch; 
    Queue<Integer> Q = new LinkedList<>();
    public int BFS(int s, int e) {
    	//좌표는 1~10000 사이임
        ch = new int[10001];
        //처음 현수의 위치를 방문 처리
        ch[s] = 1;
        //현수의 위치를 큐에 넣는다.
        Q.offer(s);
        //현수부터의 거리는 0
        int L = 0;
        while(!Q.isEmpty()) {
            //사이즈는 1, 3, 9, 27 ...
            int len = Q.size();
            //해당 레벨에서 노드들(거리들) 탐색
            for(int i = 0; i < len; i++) {
                int x = Q.poll();
                //현재 노드(거리)에서 3가지 점프
                for(int j = 0; j < 3; j++) { 
                	//점프한 거리
                    int nx = x+dis[j];
                    //현재의 거리에서 점프한 거리가 송아지의 위치이면 바로 리턴
                    if(nx==e) return L+1;
                    //1.좌표값이 1~10000이므로 해당 좌표 넘지 않도록 제한
                    //2.방문한 곳을 또 처리할 필요가 없음
                    if(nx >= 1 && nx <= 10000 && ch[nx] == 0) {
                        //방문 처리
                        ch[nx] = 1;
                        //3개의 좌표 값을 각각 큐에 넣어준다.
                        Q.offer(nx);
                    }
                }
            }
            //해당 레벨에서 3가지 점프하여서 큐에 넣어뒀다면 자식 노드들도 탐색
            L++;
        }
        return answer;
    }

    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));
    }

}