설명

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

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

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

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

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

코드

public class Calf {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();

        Calf c = new Calf();
        int bfs = c.bfs(input1, input2);
        int bfs2 = c.bfs2(input1, input2);
        System.out.println(bfs);
        System.out.println(bfs2);
    }
    public int bfs(int start, int calf){
        int count = 0;
        Jump jump = new Jump(start);

        while(jump.data != calf){

            int min = Integer.MAX_VALUE;
            int m = Math.abs(calf - jump.minus);
            int p = Math.abs(calf - jump.plus);
            int j = Math.abs(calf - jump.jump);

            min = Math.min(min, m);
            min = Math.min(min, p);
            min = Math.min(min, j);
            if(min == m) jump = new Jump(jump.minus);
            else if(min == p) jump = new Jump(jump.plus);
            else if(min == j) jump = new Jump(jump.jump);

            count++;
        }

        return count;
    }

    int[] dis = {1,-1,5};
    int[] ch;
    Queue<Integer> que = new LinkedList<>();
    public int bfs2(int s, int e){
        ch= new int[10001]; //방문 체크 배열
        ch[s] = 1;
        que.offer(s);
        int level = 0;
        while(!que.isEmpty()){
            int length = que.size();
            for(int i=0; i<length; i++){
                int x = que.poll();
                for(int j : dis){
                    int nx = x+j;
                    if(nx==e) return level+1;
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        ch[nx] =1;
                        que.offer(nx);
                    }
                }
            }
            level++;
        }
        return 0;
    }
}
class Jump{
    int data;
    int plus;
    int minus;
    int jump;

    public Jump(int data) {
        this.data = data;
        plus = data+1;
        minus = data-1;
        jump = data+5;
    }
}

이번 문제는 BFS문제인데 이진트리 탐색이 아닌 상태트리 탐색이라는 점이 저번 문제와 다른 점이다.

위와 같이 트리의 탐색을 진행하였지만 이번에는

위 그림과 같이 트리가 만들어진다고 생각하면 된다. 정말 전공이면서 이 부분을 떠올리지도 못했다... 무조건 이진트리로만 풀려고 하니 절대 풀리지 않았지 ㅜㅜ

그래서 내가 풀이한 방법 먼저 설명을 해보자면 저번처럼 class를 직접 만들어서 값을 넣어 비교하는 방법을 선택했다. 그래서 Jump class를 만들었고 Jump class는 생성되어질때 data 값을 받으며 그 값으로 3개의 값을 만들어낸다. 그 후에는 코드에 적힌 그대로 3값으로 송아지 위치 값과 비교하여 절대값이 가장 작은 수를 찾아내 그 값으로 다시 Jump class를 생성하여 3개의 값을 계속해서 비교해 나가는 것이다.

이제 강의에서 풀이한 방법을 보자

강의에서 풀이한 방법에는 class를 따로 생성하지 않고 queue를 활용하여 값을 저장해서 사용한다. 이전에 우리가 풀었던 방식과 아주 유사하며 이 방법으로 익혀둬야 나중에 어떤 문제가 나오든 바로 대입할 수 있을것 같다...ㅜㅜ

ch[s] = 1;
que.offer(s);

코드를 간단하게 설명하자면 체크 배열인 ch의 index를 1로 변경하고 최초 들어온 s 값을 queue에 넣는다.

	while(!que.isEmpty()){
            int length = que.size();
            for(int i=0; i<length; i++){
                int x = que.poll();
                for(int j : dis){
                    int nx = x+j;
                    if(nx==e) return level+1;
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        ch[nx] =1;
                        que.offer(nx);
                    }
                }
            }
            level++;
        }

while을 통해 que가 비어있을 때까지 반복하는 것인데 dis 배열에 {1,-1,5}를 각각 연산하여 자식 노드를 만든다.

트리의 단계별로 모든 노드들을 연산하여 만든다고 생각하면 좋을 것 같다.

ch 배열은 다음과 같이 index 5는 이미 검사했으므로 체크를 한다.

5를 넣고 실행했을때 트리의 결과는 다음과 같고

que에는 6 4 10이 들어가있어 다시 실행한다.

그리고 que에 들어 있는 값들을 다시 검사하므로 모두 실행하고 난 후 ch배열은

다음과 같으며

(그림을 하나에 다 담으려니 기괴한 그림이 나와버렸다...)
이런 트리의 값들을 찍어내는데 자식 값이 없는 노드들은 ch배열에서 이미 값을 체크했으므로 실행을 하지 않았기 때문이고 15는 송아지의 위치 값인 14를 찾았으므로 반복문이 종료되어 더 이상 자식 값을 만들지 않았기 때문이다.

이렇게 그림을 그려가면서 이해를 해보면 더 좋은것 같다. 내 그림이 형편 없어 도움이 안되겠지만 ㅜㅜ 직접 그려보면 해당 코드를 이해하는데 큰 도움이 될것이다! 강사님도 꼭 직접 그려보라고도 하셨고!

BFS는 최단거리를 구하는 좋은 알고리즘이며 위 코드와 같은 방법을 익혀두면 사용하기 정말 편한 알고리즘인거 같다!