[JAVA] BFS - 송아지 찾기

문제

- 현수와 송아지의 위치가 주어질 때, 현수가 송아지의 위치로 갈 수 있는 최소의 점프 횟수를 구해라

- 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5 이동 가능하다.

 

레벨 0에서 루트 노드를 큐에 넣어주고, 방문 체크를 해준다.

while문에서 큐의 사이즈를 구해준다. // 큐의 사이즈 = 레벨에 있는 원소의 개수

큐의 사이즈 만큼 for문을 돌려준다. 

큐에서 원소들을 꺼내준다. // 레벨에 있는 원소들

원소들이 다음에 갈 수 있는 위치들을 계산해준다. 

다음 위치의 원소들이 범위에서 벗어나지 않고, 방문하지 않았던 곳만 큐에 넣어준다.

이때, 다음 레벨의 원소가 송아지의 위치일 경우 현재레벨+1을 return 해준다.

없을 경우, for문이 종료되고 해당 레벨의 순회는 종료되어 레벨을 +1 증가 시켜준다.

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int answer = 0;
    int[] dis = {1, -1, 5};
    int[] ch; // 체크 배열
    Queue<Integer> Q = new LinkedList<>();

    public int BFS(int s, int e){
        ch = new int[10001]; // 좌표는 1부터 10000까지
        ch[s] = 1; // 방문 체크
        Q.offer(s); // root 노드
        int L = 0; // 레벨 0에서 시작
        while(!Q.isEmpty()){
            int len = Q.size(); // 큐의 크기 = 레벨에 있는 원소
            for(int i=0; i<len; i++){
                int x = Q.poll(); // 레벨에 있는 노드 꺼내주기
                //if(x==e) return L; // 송아지 찾는 방법 1 : 레벨에 송아지의 위치가 존재하면 return
                for(int j=0; j<3; j++){ // 이동할 수 있는 3가지 경우의 수
                    int nx = x + dis[j]; // 현재노드 + 이동거리 = 이동한 노드의 위치
                    if(nx==e) return L+1; // 송아지 찾는 방법 2 : 다음 레벨에 송아지가 있다는 뜻
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        // 범위에서 벗어나지 않고, 방문 체크 안한곳만
                        Q.offer(nx);
                    }
                }
            }
            // for문 종료되면 레벨 증가
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int s = 5;
        int e = 14;
        System.out.println(T.BFS(s, e));
    }
}