[JAVA11/알고리즘] 7-8 송아지 찾기 1 (BFS : 상태트리탐색)

 💬 문제

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

 

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

 

송아지는 움직이지 않고 제자리에 있다.

 

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

 

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

🔨 입력

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.

출력

 

🔨출력 

점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.

👊🏻 예시 입력 1 

5 14

👊🏻 예시 출력 1

3

 

💡 해결

제목부터 BFS를 사용한다고 되어있으므로 편하게 BFS를 활용하여 풀어보았다.

 

한번의 점프로 앞으로 1칸, 뒤로 1칸, 앞으로 5칸을 갈 수 있다고 하였다.

입력받은 S값을 루트 노드로 잡고, 자식노드를 매 노드마다 3개씩 생성한다.

+1, -1, +5를 각각 해준 값을 입력한 자식노드를 생성한다.

 

자식노드를 생성하면서, 중복되는 값들이 생성될 수 있다. 

예를 들자면, +1을 하고 -1을 하면 다시 원위치로 오게 된다.

속도를 올리고자, 이런 경우에는 그 자식노드를 생성하지 않기로 한다.

ch라는 int형 배열을 만들어서 만약, 노드의 value 값을 인덱스에 넣어, 그 배열값이 1이면, 방문한 적이 있는 위치이고 0이면 방문한 적이 없는 위치라고 한다.

 

퀄리티 ㅈㅅ

 

상당히 퀄리티가 낮은 예시를 만들어 보았다.

왼쪽 자식노드는 +1, 가운데는 -1, 오른쪽은 +5를 더해준다.

x 표시를 해둔 5는 루트노드인 5와 값이 일치하여서 더이상 만들어주지 않는다.

그리고 원하는 14가 나오게된다면 그 노드의 레벨값이 곧 답이된다.

 

 

👨🏻‍💻  CODE
 

import java.util.*;

public class Main {
    static int[] dis = {1,-1,5};
    static int[] ch;
    static Queue<Integer> Q = new LinkedList<>();
    public static int BFS(int s, int e){
        ch = new int[10001];
        ch[s] = 1; //ch 배열의 값이 1이면 방문함, 0이면 방문안함을 의미
        Q.offer(s);
        int L = 0;
        while(!Q.isEmpty()){
            int len = Q.size();
            for(int i=0; i<len; i++){
                int x = Q.poll();
                for(int j: dis){
                    int nx = x+j; // nx는 자식노드를 의미
                    if(nx == e) return L+1;
                    if(nx>=1 && nx<=10000 && ch[nx] ==0){
                        ch[nx]=1;
                        Q.offer(nx);
                    }
                }
            }
            L++;
        }
        return 0;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int e = in.nextInt();
        System.out.println(BFS(s,e));
    }
}

 

 

💪🏻 결과