[JAVA] 알고리즘 : 송아지 찾기(BFS)

 

 

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

class Main{
    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];
        ch[s]=1;
        Q.offer(s);
        int L=0; // 루트 노드는 레벨이 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++){ // x의 자식 노드들
                    int nx = x+dis[j];
                    if(nx==e) return L+1; // 답을 찾으면 현재 레벨+1 리턴(자식 노드이므로)
                    if(nx>=1 && nx<=10000 && ch[nx]==0){ // 범위 안에 있고 방문하지 않았다면
                        ch[nx]=1;
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        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));
    }
}

 

 

현재 위치를 루트 노드로 시작해 현재 위치로부터 +1, -1, +5 한 위치의 값들을 자식 노드로 하여 큐에 집어넣고,

레벨을 증가시키며 탐색한다. 

이 때 한번 방문한 값은 검사할 필요가 없으므로 체크 배열로 방문을 했는지 체크한다.

자식 노드 중에 답을 찾으면, 현재 레벨을 리턴한다.