BFS상태트리_송아지찾기

코드

import java.util.*;

class BFS송아지찾기상태트리 {
    int answer=0;
    int[] dis={1, -1, 5};
    int[] ch;
    
    Queue<Integer> Q = new LinkedList<>();
    public int BFS2(int s, int e){
        ch = new int[10001]; // 상태체크 배열
        ch[s]=1; //시작위치 방문 체크
        int L = 0;
        Q.add(s); //시작 
        
        while(!Q.isEmpty()) {
            int length = Q.size();
            for (int i = 0; i < length; i++) {
                int v = Q.poll();
                for(int move : dis) {
                    int nextV = v+ move;
                    if(nextV == e) return L+1;//목적지 찾음
                    if(0<nextV && nextV <=10000 &&ch[nextV]==0) {//ch[nextV]==0 첫방문
                        ch[nextV] =1; //이제 방문 표시
                        Q.add(nextV);
                    }
                }
            }
            L++;
        }
        return 0;
    }
    
    

    public static void main(String[] args){
        BFS송아지찾기상태트리 T = new BFS송아지찾기상태트리();
        int start = 5; // 시작 위치
        int end = 14;  // 목적지 위치
        System.out.println(T.BFS2(start, end));
    }   
}

---

결과

3

---

앞 뒤로만 갈 수있다고 가정하고, 시작 위치에서 목적지까지 최소 회수를 찾는 문제다.

1~10000은 주어진 경계값으로 무시해도 된다.

핵심은 주어진 경계값 만큼에 상태값을 측정할 배열을 만들어 내가 방문한 곳인지 아닌지를 체크하는 것이다. 10001로 생성한 것은 배열이 0부터 시작이라 보기 편하게 1부터 사용하려고 한 것

상태트리

ch 배열이 중요한 이유는 재방문을 줄여 시간복잡도 개선과 무한반복을 방지하기 위함이다.

위 상태트리에선 공간 문제로 5가 왜 큐에 저장이 안됐는지만 표시했다.

위 상태 트리 L2 직후 상태

끝까지 탐색한다면 위 상태 노드를 만다고 종료할 것이다.