송아지 찾기

송아지 찾기

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.

입력 설명

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

출력 설명

점프의 최소횟수를 구한다. 답은 1이상입니다.

입력 1

5 14

출력 1

3

입력 2

1 100

출력 2

21

틀린 구현 코드

public class 송아지찾기_BFS {
    static int[] dir = new int[3];
    static int cow;
    static int answer=1;
 
    static ArrayList<Integer> markedList = new ArrayList<>();
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int cur = in.nextInt(); //현수 위치
        cow = in.nextInt(); //송아지 위치
 
        Node root = new Node(cur);
 
        dir[0] = 1;
        dir[1] = -1;
        dir[2] = 5;
 
        bfs(root);
 
        System.out.println(answer);
 
    }
 
    static void bfs(Node root){
        Queue<Node> queue = new LinkedList<>();
        markedList.add(root.data);
        queue.offer(root);
 
        int check = 0;
        int k=1;
 
        while(!queue.isEmpty()){
            Node r = queue.poll();
            if(r.data==cow) break;
 
            if(check==Math.pow(3,k)){
                check = 0;
                answer++;
                k++;
            }
            for(int i=0;i<3;i++){
                Node n = new Node(r.data+dir[i]);
                if(!markedList.contains(n.data)){
                queue.offer(n);
                markedList.add(n.data);
                }
            }
            check++;
        }
    }
 
 
    static class Node{
        public Node(int data) {
            this.data = data;
            adjacent = new LinkedList<>();
        }
        int data;
        LinkedList<Node> adjacent;
    }
}

문제점
1. bfs기본 구현에 충실하려한 나머지 필요없는 Node class 선언
2. 큐의 레벨을 세야 하는 문젠데 레벨단위로 셀 수 없게끔 큐에서 하나씩 빼서 비교하는 식으로 구현함. -> 불필요한 계산부분도 넣음.
3. 해당 노드가 이미 확인한 값인지 비교함과 동시에 수 범위 값도 비교해야함. 왜냐하면 -1을 계속 더하다보면 음수값이 생길 수 있고, 또한 수를 계속 더하다보면 10000을 넘는 수가 생길 수 있으므로 확인 필요.

모범 답안 참고 후 구현 코드

static void bfs(Node root){
    int L = 0;
    Queue<Node> queue = new LinkedList<>();
    markedList.add(root.data);
    queue.offer(root);

    while(!queue.isEmpty()){
        int len = queue.size();
        for(int i=0;i<len;i++){
            Node r = queue.poll();
            if(r.data == cow){
                System.out.println(L);
                return;
            }
            for(int j=0;j<3;j++){
                Node n = new Node(r.data+dir[j]);
                if(!markedList.contains(n.data) && n.data>=1 && n.data<=10000) {
                    markedList.add(n.data);
                    queue.offer(n);
                }
            }
        }
        L++;
    }
}

수정사항
1. queue에서 하나씩 빼서 그때마다 수를 세는게 아닌, queue의 사이즈만큼 즉 같은 레벨에 있는 노드들을 다 돌고 난 후 수를 세는 방식으로 수정.

문제점
1. 레벨을 세는 방식 자체는 수정됐으나, 불필요한 Node class 사용. 값 비교이므로 int배열로 충분.

모범 답안

    static int[] dir = {1,-1,5};
    static int[] ch;
    static Queue<Integer> queue = new LinkedList<>();

    static void bfs(int cur,int cow){
        ch = new int[10001];
        ch[cur] = 1;
        queue.offer(cur);
        int L = 0;
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i=0;i<len;i++){
                int x = queue.poll();
                if(x==cow){
                    System.out.println(L);
                    return;
                }
                for(int j=0;j<3;j++){
                    int nx = x+dir[j];
                    if(nx>=1 && nx<= 10000 && ch[nx]==0){
                        ch[nx] = 1;
                        queue.offer(nx);
                    }
                }
            }
            L++;
        }
    }