강의정리 - 이진트리순회(BFS)

- 이진트리 순회(넓이우선탐색: 레벨 탐색)

public void BFS(Node root){
       Queue<Node> Q = new LinkedList<>();
       Q.offer(root);
       int L=0;
       while(!Q.isEmpty()){
           int len = Q.size();
           System.out.println(L+" : ");
           for(int i=0; i<len; i++){
               Node cur = Q.poll();
               System.out.print(cur.data);
               if(cur.lt!=null)
                Q.offer(cur.lt);
               if(cur.rt!=null)
                Q.offer(cur.rt);
           }
           L++;
           System.out.println();
       }
    }

- 송아지 찾기 (BFS)

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

 1) 송아지는 움직이지 않고 제자리에 있음

 2) 현수는 한번의 점프로 앞으로 1, 뒤로1, 앞으로 5를 이동할 수 있음

 3) 최소 몇번의 점프로 송아지의 위치까지 갈 수 있는지 구하는 프로그램 작성

int answer = 0;
    int[] dis={1,-1,5};
    int[] check;
    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;
        while(!Q.isEmpty()){
            int len = Q.size(); //level에 있는 원소의 갯수 
            for(int i=0;i<len; i++){
                int x = Q.poll();
                
                for(int j=0; j<3; j++){
                    int nx = x+dis[j];
                    if(nx==e) return L;
                    if(nx >=1 && nx<= 10000 && ch[nx]==0){
                        ch[nx] = 1;
                        Q.offer(nx);
                    } //방문했는지 체크   
                }
            }
            L++;
        }
        return 0;
    }
        
        return answer;
    }