BFS_상태트리 탐색

🔑 최단거리 알고리즘 키워드

BFS(레벨탐색)는 (이진트리를 포함한 상태트리에서) 주로 최단거리 알고리즘에 사용됨
최단거리 알고리즘 키워드: “최소 횟수인 거리”

✅ 송아지 찾기

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서
송아지의 위치까지 다음과 같은 방법으로 이동한다.
한번의 점프로 각각 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
최소 몇 번의 점프로 송아지의 위치까지 갈 수 있는지 구하세요

• 단, 직선의 좌표 점은 1부터 10,000까지 이다.
• 답은 1 이상이며 반드시 존재한다.

🟠 Problem Solving Strategy

✔️ 최단거리 알고리즘을 풀기 위해 BFS사용

• 현수의 위치 5가 루트 노트
• 루트 노트에서 다음 레벨(🟰점프)로 가기 위한 경우의 수는 3가지 (-1, 1, 5)이다.
• 따라서 점프 횟수 🟰 레벨
• 단, 시각 복잡도를 줄이기 위해 이미 나왔던 숫자(이미 방문한 노드)는 큐에 넣지 않는다.

✔️ 트리 구조

🟢 코드 구현

class Main {
    int answer=0;
    int[] dis= {-1, 1, 5}; //점프로 갈 수 있는 3가지 경우
    int[] ch; //내가 방문 했는지 안했는지 확인하기 위한 체크 배열, 방문 하면 1
    Queue<Integer> Q= new LinkedList<>();

    public int BFS(int s, int e){
        ch= new int[10001]; //좌표 최대 거리, 0번 인덱스는 사용하지 않는다

        ch[s] =1; //출발지점 s방문
        Q.offer(s);

        int L=0; //레벨

        while(!Q.isEmpty()){
            int len= Q.size(); //해당 레벨 노드 개수
            for(int i=0; i< len; i++) {
                int cur= Q.poll();
                if(cur==e) return L; //답 찾고 리턴
                for(int j=0; j<dis.length; j++){ //-1, 1, 5를 각각 점프
                    int nx= cur + dis[j];
                    if(nx>=1 && nx <= 10000 && ch[nx] == 0){ //ch배열 벗어나면 안됨, 좌표 범위 제한 //또 방문한 노드인지 확인
                        ch[nx]=1; //방문 했다고 체크
                        Q.offer(nx); //방문 안했으면 큐에 넣기
                    }
                }
            }
            L++;
        }
        return 0; //답은 반드시 있다고 했으니 L이 리턴되겠지만 반환형이 int이므로 임의의 숫자 넣기
    }
    public static void main(String[] args) {
        Main T= new Main();
        Scanner sc= new Scanner(System.in);
        int s= sc.nextInt();
        int e= sc.nextInt();
        System.out.print(T.BFS(s, e));
    }
}

//⭐️input:
//5 14
//⭐️output:
//3

🔵 Things I learned

• 점프로 갈 수 있는 거리가 {-1, 1, 5} 이니까 3갈래로 나눠진다.
• 점프를 한 번 할 때마다 1레벨씩 늘어난다.
• 한번 방문한 노드는 방문하지 않기 위해 체크배열 ch를 만든다.
• 방문하면 ch값이 1, 방문 아직 안했으면 0
• 방문한 노드는 큐에 추가하지 않음
• 큐에서 cur을 하나 빼서 정답이랑 똑같은지 확인! 같으면 지금 있는 레벨 L 리턴
• 점프할 수 있는 {-1, 1, 5}를 각각 뛰면서 값을 구함
• 구한 값이 ch배열의 범위 내에 있고, 아직 방문하지 않은 노드라면 큐에 추가
• 그리고 방문 했다고 추가할 것
• 현재 있는 레벨을 다 참색했다면 다음 레벨로 넘어가기 L++

🟢 조금 더 빠른 코드

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;

        while(!Q.isEmpty()){
            int len= Q.size();
            for(int i=0; i< len; i++) {
                int cur= Q.poll();
                for(int j=0; j<dis.length; j++){
                    int nx= cur + 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 sc= new Scanner(System.in);
        int s= sc.nextInt();
        int e= sc.nextInt();
        System.out.print(T.BFS(s, e));
    }
}

//⭐️input:
//5 14
//⭐️output:
//3